CodeCaster

I'm sorry this will be a little off-topic, but the proprietary scripting language I am using, which doesn't even have a name, is closest to C++.

Basically, what I need to do is discover a clear path to a grid corrdinate given the location of obstacles (some of which are moving). I have the following variable to use to check for clear path

bool LineOfSight (true if clear path from point a to point b)

Basically, the fact that some obstacles are moving is irrelevant because this function will be called many times per second from a main loop, constantly building a new path to its target point so as to adapt to changing surroundings.

Right now, all my function is capable of doing is cycling through every grid coordinate in a certain range with a step of 20 units, and finding a common point from which the target point and the starting point have a common line of sight and moving to that point, then on to the target but this will not work in many circumstances where two, three or even four turns have to be made to navigate a maze of obstacles.

This seems like such a basic program to write but it is totally frying my brain! All I am really looking for is some pseudocode describing the basic logic of making this happen... If anyone can give me some basic insight or point me in the right direction for help, my sanity would be forever in your debt!

Thanks!

EverLearning

do you mean like there's several objects with different initial coordinates that are trying to get to the same target?
or do you mean like you have to repeat the process (for one object) several times in a row?

__________________
got math? yumm...

"All men by nature desire to know" -Aristotle, Metaphysics

CodeCaster

let's say I am trying to navigate a maze, and the walls shift around every few seconds. I have to discover a new path to my target every few seconds so as to adapt to the changing environment. All i have to see if the way is clear to the next position is the LineOfSight function.

To answer the question directly, no, i am the only one trying to reach the target location, but there are things moving around trying to get in my way that I need to avoid. I have actual location coordinates for the moving obstacles, but the walls need to be discovered using only line of sight.

DaWei

The problem as you describe it is not amenable to solution if the obstacles can move from point to point as rapidly as the seeker. Consider the following extreme condition. If the seeker moves to an adjacent point, the obstacle merely needs to move to the intervening, "blocking" point. If the obstacles move more slowly, but the number of intervening points to the target is larger, the solution can still be unattainable.

I would suggest that "clear line of sight" is immaterial to a solution for a properly defined problem. Occupancy of adjacent step-points defines a possible path at any given moment.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

CodeCaster

The following is a more accurate view of my situation:


In the above example, i would want the path to be built to right 2 units, then up 2 units, then left 2 units, so as to avoid the rock, the tree, and the enemy, which could even be following behind me. However, if the enemy were to move 1 unit to the left, then the point up and to the left of me would become the most prudent choice. Currently, my script would notice that the point directly up and to the left of my starting position shares a line of sight with both myself and my target, so I would be moved there and killed by the enemy sitting adjacent to that point if he had not yet moved.

The trees and rocks are stationary objects, and LineOfSight will return false if one is in your way, however, it will not return false if an enemy is in your way. You have to use the enemy's current (x,y) position in order to avoid him.

I really appreciate you giving this some thought! Please let me know if there are any more details I can provide!

DaWei

Well, to be truthful, it's difficult to help in any significant way if you fail to describe your problem (and goals) clearly. Now we have moving and non-moving objects. In terms of moving obstacles, the problem remains the same --given the same opportunity to move, and the ability to move at the same rate, if the enemy obstacle has intelligent choice, he may head you off at the pass and prevent your ever getting by. If, on the other hand, you have the ability to choose, and the enemy is stuck with random movements, you may or may not win. It isn't even worth wasting thought on if the parameters are unknown or undecided upon. It's like playing a game and only the opponent knows the rules (plus, is able to change them at will).

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

CodeCaster

for the purposes of this application, we can assume that the enemy is just randomly roaming from point to point, and will only harm me if I land on a point adjacent to him or directly on top of him. the enemy does not have intelligent choice.

Actually, now that I think about it... It's more or less irrelevant that the enemy is moving. for this purpose, it can be considered stationary due to the fact that a new path will be calculated much faster than the enemy is capable of moving, thus avoiding it the same way I would avoid a tree or rock. This is taking place in a free-roaming environment, so there is really no way any combination of obstacles could totally block all paths from point A to point B.

Really all I need is a pathfinder for a simple maze-type video game... I could adapt something like that fairly easily to do what I want, but I can't seem to find anything like that as I surf around the web...

Thanks again!

DaWei

This is NOT true with a mobile enemy that can move at the same rate as the seeker. Just consider that if YOU sidestep, HE may sidestep into your path. If you step to the other side, HE may step in that direction also. You may have nearly bumped into someone on the street, only to find you're both stepping back and forth to the same side at the same time. Think also of Pacman/Ms.Pacman where the opponent can be faked into commiting to one direction and has a relatively small probability of reversing. That gives the player the opportunity to seek the goal before the opponent can zero in on it again. You can also program the opponent(s) with differing levels of "aggressiveness", so that their choice of direction at any given point is some ratio between a random direction and a direction that tends to intercept the player.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

CodeCaster

we can also assume that the enemy moves at a lower rate of speed than the seeker and moves in one direction until he decides to sit still for a while, then moves in a random direction for a while, and recycles.

The Dark

Try using an algorithm like this:

Start with a grid the same size as your map with all zeros. Mark each clear point around the target with a 1, then visit each point marked with a 1 and mark each clear point (that is not already marked), with a 2. Repeat this until you try to mark the starting point.
Once you hit the starting point, just follow the trail back, you now know how long the trail is, you then just have to look around the current point in the trail for the next step (which will be marked with a distance value of one less than the current distance).