Interesting Pathfinding Problem

I'd still use A* - if each node (grid cell) is linked to the eight adjacent cells on the above layer I think the algorithm would work correctly to comply with the fact that time only goes in one way.
There is always the issue that a path may not exist. In your case I can think of no certain way to deal with this because time obviously extends infinitely. You may just need to cap the maximum time that you project to.

Edit: Thinking about it now, I don’t think A* would work at all.

Anyhow, good luck with this,
Jackson Allan

[Edited by - jack_1313 on December 22, 2004 10:49:03 PM]

Sorry to be bearer of bad tidings, but...

This is just a discrete version of path planning using deterministic transitions of a state machine for the domain. Your representation doesn't, to me at least, seem to offer anything of an improvement over any other current method for temporal planning. All your grid is doing is enumerating a model for the evolution of the domain using an array. This is typical collision detection. Indeed, when your domain starts to increase in size, you'll need to abandon this representation and move back to a node based representation.

If you want a more complex example of the application of your idea, look at stochastic processes (where there is uncertainty in your domain and its evolution) represented by Hidden Markov Models.

Cheers,

Timkin

I think A* might work, with some special considerations. A* is a great flexible little algorithm.

There is the problem with the time, how much time does it take for the objects to move, and how much time does it take for the unit to move. If the objects take twice as much time to move then the unit, for instance, then when queueing the costs of the open nodes, the nodes that go up a layer, wich means that the unit is going to wait for the objects to move and then chose a next move, well these nodes will cost twice as much, because the objects move slower, and that means the unit will have to wait more, wich means the move(wich is to stay for a while and then move) will costs more.

Then there is the 3D aspect applied to time, in A* we add to the open list all the nodes that surround the current node, but here we can't exactly do that, we can't go to the nodes down, because those would be go back in time.

Then the distance to the destiny, when calculating the costs, we add the current costs that it took to get to the node we're evaluating with the heuristic, that is a guess of how much will it take to reach the end, well this heuristic will have to calculated using no the original node, but the one in the current time frame. If you calculate the heuritic based on the inicial node you'll get a higher heuristic then it needs to be, it will still be optimal, but will take longer.


There are probably other quirks that i don't recall right now, but i'm sure others will point them out or you'll find them when you code it.

Timkin and others, thank you for your reply to my question. Good news or bad, any information you can give me is helpful.

To give a better example of the problem I am trying to figure out.

Lets say we have a table, 10 green marbles, and 1 red. I can control the red marble but none of the green.

Lets say I roll all the green marbles across the table at once from random directions and speed.

Now I have to move the red marble across the table from one side to the other, but I have to do it in such a way that I can not pass within 2 inches of any other marble.

Now, if the Green marbles were stationary, it would be simple to find a path through the area with A* or any other path finding algorithm, but given that the marbles are moving and I can't pass within 2 inches of any marble as I move across, and I do want to move across. I can stop if no path exists, but optimally, I want to be able to get across.

Can you give me any pointers on how to go about solving this problem? In the idea I had to solve it, it would be more or less pathfinding through small instances in time to find my way across.

More ideas anyone?

I made an old game like this a while ago, where You had to move across a 5x5 grid (then a 7x7 or level two, and so on...) Without getting hit by arrows. The arrows were shot from bowmen on the right, left, top and bottom of the screen. Before starting you know at what point in time each bowman would shoot, some would shoot every fourth turn, some on every even turn, some on every odd turn, and some on sporatic turns like the 1st 3rd and 4th, over and over again.

It was a tough little game to beat, because you had to make your way across the grid and there were arrows everywhere!


And i I were solving it I would use recursion to make a list of all the possible moves, and then branch out. Also when it figured out the position at every step of the tree, it would find the new position based on the old position and moving everything 1 space to the right.

This is silly. Scuba, What you're describing IS an application of A*!

Think about it. A* is not defined to work in 2D, it's more abstract than that. It works over graphs. A common use of A* is over a graph of squares in a grid, with adjacent open squares being mutually connected to each other -- the application we all know and love...But there's nothing saying that you couldn't use A* in a graph of connected cubes in 3D, and that you couldn't restrict the edges between nodes to all be directed forward in one of the dimensions (time).

So yes, this is an interesting application of A*...but it's still A*. If you still don't see it, read up more on the abstract graph algorithm itself and think about the myriad applications it could be used for (a common example besides our 2D grid is to solve the 8- or 16-puzzle).

Jack does bring up an interesting point though -- you'd need to put a cap on time. A* only really works well on finite graphs, heh...

I know it's an application of A*. I understand how it works. But I also know it works at finding a path through weighted and non-passable nodes. What do you do though when every step you take forward in the graph, all the node values shift? It doesn't work so well anymore. That's why I posted the idea that I had, so in instances when I move through a graph, when I node blocks my current path, but I am past that node in time, I don't care where it's at as long as Im more than a certain distance away from it.

In my idea, I would say, look ahead over say, 30 seconds, or some fixed length of time, with a specifically defined time step inbetween, say .5 seconds, so I would have a graph that is 10 wide, 10 long and 60 high for example. Then as I move through, it would be the same as searching a 10 by 10 graph, just every .5 seconds, I move up a level.

In this problem, I can run a simulation beforehand a see where all the objects are moving and at what speed, so I simply need to find a path between the objects that allows me to maintain a certain distance between me and any other object.

Timkin said he was the bearer of bad news and that this is a common problem with an already defined answer. I was curious if I could get an example from the information he gave me.

I think my idea would work, but I wanted some feedback from you all because many of you are my peers and peer reviews = good.

I'd think that the problem is no more complex than adversarial searching.

On node 1 you have four choices, 0-4 of those can lead to a dead end. at each of those nodes you have 0-4 choices that dont lead to a dead end and so on, its still just a search space, just that each node has unique options available by the time you calculate it, because the state of the search space changes with depth (time0

The only one problem would be the interval that you are evaluating the other objects movement at when working out a cost for them, if it happened that you were analysing two positions along the same path if there is big enough gap between those two positions you may have an equal cost for an object which travels between the two points and when you actually traverse the path you may have actually hit the object.

A solution to that is to check if the lines intersect instead of just evaluating the distance to the moving objects, or in your case a capped cylinder (as you wanted to be a certain radius away from other objects rather than just avoid collision).

So as you have obviously thought through by now you just penalise any path which has a segment which intersects one of your moving objects, it just comes down to if you also apply a penalty to ones which almost collide so you will get the clearest possible route.

Good luck with it and make sure to report back how it went.

Quote:

Original post by scubabbl Timkin said he was the bearer of bad news and that this is a common problem with an already defined answer. I was curious if I could get an example from the information he gave me.

Check out the D* algorithm... (Dynamic A*), it does exactly what you want to do. The other way is to use a Markov model to represent the system. If you have perfect information - i.e., you know exactly the initial state of the system and the process model governing it - then finding the solution is merely an optimisation problem. If you don't have perfect information, then you can still apply any of the algorithms for probabilistic planning to the problem.

One question: Is this supposed to be a real-time control system? Or will the controller of the red ball be given complete information before it enacts its plan?

Timkin

The user would have knowledge of all other object's location, speed, and direction of movement. All the information is readily available to the system before it begins its search.

As long as your marbles dont change direction due to your objects position its is fairly simple (and just needs a slightly more complex heuristic-map mechanism).

Use an array of 'map' time increments (each a 2d grid) The time increment should be largest step to get a 'good enough' approximation of your avoidance radius -- probably something like time = smallest_avoidance_radius / 2 * maxvelocity .

Each Map will also be a cartesian grid (squars granular size to be something like 1/4 of a avoidance radius) with squares marked out as 'blocked' where the marbles are at that point in time. (static terrain blocks should be marked also...)

You prebuild the map set once at initialization.

A* open nodes will have a 'time' attribute (map index the A* cycle will be applied to)

The same A* mechanism will be used to find the path -- the heuristic check will apply the correct time map to the current test position of the open node.

The objects collision check may have to test a pattern of grid squares (could be a fixed set of offsets from the objects centerpoint to increase efficiency

A hierarchical system could be added to minimize the number of grid squares checked (ie a second higher map representation where each square represents 4x4 or 8x8 of the finer maps (the large squares have a blockcheck flag which is originally set if any one of the 4x4 or 8x8 are blocked -- forcing a more detailed check etc...)

Another optomization may be how many total time increment maps to build initially
(only adding additional ones if the path needs them).


Alternately I suppose you could use a quadtree to represent each map time increment (especially if its a large map and sparse (low marble count and/or static blocking terrain).

This should be possible as a straightforward A* problem. Though, as always, getting the right hueristic is the tricky part.

I think you may just be overlooking what type of "map" representation would be best to perform your pathfinding on. Consider an auxillary map containing "t" values for each of your green marbles, something like

typedef struct {
int green_t[NUM_GREEN_MARBLES];
int any_other_necessary_fixed_obstacle_flags;
} AUX_CELL;

AUX_CELL aux_map[ROWS][COLS];

Now simulate the entire (apparently straight line?) path for your time period of each green marble, at at each tick of t, insert that t into the map at the marble's current location.

Now, when pathfinding, keep track of the same units of "t" for each of your path states of the red marble's position. At any grid cell then, you can determine the difference in time between when any green marble occupies it and when the red marble occupies it, let's call that "dt[n]" for red_t-green_t[n]. Your hueristic may then be determined by the desire to keep all |dt[]| > 2 (or other value). In other words, any green marble may HAVE been or may WILL be at this location no less than 2 ticks from when the red marble "wants" to be there.

To visualize: Imagine a heightmap where when |dt|>2 you assign the value 0, otherwise the value 100. You now want a path through that "canyon" - easily done with A*.

Basically the assumption is that you can encode distance as time. (because it sounds like all motion vectors are known in advance) If your marbles are moving at different speeds you may have to use specific values (instead of hardcoding "2") for each marble. In other words, fast marble #1 might require |dt|>4, while perhaps slower marble #2 only requires |dt|>1 to avoid collision. You don't give enough information for me to suggest a better time-to-grid-distance conversion, but it should be straightforward.

Further thoughts: if any green marbles are moving REAL slow, such that they might occupy more than a single tick in a single grid cell, then you'd want to modify AUXCELL to track both green_enter_t[] and green_exit_t[], then compare that red_t is less than green_enter_t-2 or greater than green_exit_t+2.

Also note that if you're stuck on the visualization I proposed earlier, that the "canyon" will shift with every tick. That's not a problem as the red marble will still be in a canyon at t+1 if at t it was in a cell where |dt|>2 (because that cell would now necessarily be at least |dt|>1).

It appears that the only variable under control of the red ball is the time (frame) at which it releases itself, correct? It's start position is fixed, it's goal is fixed, it's velocity once released is fixed, yes? This was my assumption when I proposed calcing red_t (d=vt, so t=d/v, so (current_location-start_location)/red_vel = red_t to reach that location) If not, for example, if there are multiple possible start locations, then you'll have to loop through each additional variable each frame looking for a path from THAT particular starting condition:

// if only release time is variable
on each frame
find a path from fixed initial state

// if additional variables introduced, for example
on each frame
for each starting position
for each additional added variable continue nesting deeper
find a path from this particular variable state

What isn't clear is if the red ball has any control over it's motion once released. In other words, if the red ball ALSO has only straight line motion, then you'll have to post-process the path to make sure (even if you get a result) that it's a straight line result. And in fact, in that case, generic A* is a poor choice as it'll spend way too much time looking for ANY path - a modified bresenham-style line-drawing routine would be better. Using same hueristic described above, "draw" your path through the grid, failing if ever |dt|>2. You can still implement it as A*, all you've done is added a straight-line-only constraint to the "generate successors" portion.

ah, Frogger
been a long time since I played that
makes me wonder how I did it as a human
probably something greedy, at most looking 2 rows ahead
and jumping backwards a lot -your path doesnt need to be optimal, does it?