Shortest Path Around Obstacles?

[Septenary]

Hey,

I'm making a game in Actionscript 3.0. It's not the first time I've made a game, so I do have a bit of experience - but that bit is all I have. So, I apologize for any newbishness in my post.

Anyway, I am having problems moving an object from one point to another, with rectangular obstacles in between. So far, my code is something like this:

1) If the object is moving towards an end point and is touching an obstacle...
2) Send two "ghost" objects clockwise and counter-clockwise around the obstacle.
3) Move the "ghosts" to the verticies of the rectangle (CW or CCW)
4) Keep moving around the rectangle until this obstacle no longer obscures the path to the end point
5) Return the shorter path around the rectangle (CW or CCW) to the object, and make the object move along this path.

For example:

http://www.NightTowers.com/private/SamplePath1.gif

Here, the object (red square) needs to get around the obstacle (black square) to the end point (green square). So, it follows the red path.

This is ok, but probably way too simple, and problems come up like this:

http://www.NightTowers.com/private/SamplePath2.gif

The second obstacle obscures the path of the ghost.

I don't like this method at all, but it was the only thing I could come up with. Creating the "ghosts" and then moving them around verticies turns out to be pretty intensive too, and, as in the final project, I plan on including much movement and graphics, I want this to be as efficient as possible.

I need a way to efficiently make the red object find this path to the green square:

http://www.NightTowers.com/private/SamplePath3.gif

Or, whatever the shortest path around the obstacles happens to be. I want the object to be able to find the shortest, "smartest" path before it actually hits the obstacle.

If I could get some help with this problem, I would greatly appreciate it!

[joran420]

use tiles(see tonypa's tile tutorial it has like 6 chapters on enemy pathfinding...its flash 8 but you can prolly figure out how to do it with AS3 from it)?


maybe?

[ArmoredSandwich]

Pathfinding is very hard. Try to search for the A* algorithm that will solve all your problem IF you are able to code it.

To get an idea:
http://www.policyalmanac.org/games/aStarTutorial.htm

I have no clue how you could get a pathfinding algorithm without a tile based game :S.

[Sirisian]

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

That's another approach which uses a non uniform grid unlike A*.

http://en.wikipedia.org/wiki/A%2A_search_algorithm
A* really isn't hard unless you're inventing it from scratch. Wikipedia has the full psuedo-code and references to articles.

[Jerryscript]

You will get great results with A* if you use a grid.

You can also use a vector based algorithm, but multiple objects in the path are a bit trickier to handle than in A*. A simple path around any object is made up of two paths which, together with the straight line between the start and the goal, form a triangle. Once this triangle is formed, you can determine the x position at which the object ends, and subdivide the triangle at that point to determine the shortcut vector that will go around it. With rectangles, that's as far as you go, with more complex geometry, you can continue to subdivide the triangle based on vectors of the object's vertices to get the shortest path.

The drawback with multiple objects is determining the intermediate goal points that together create the shortest path. This is where A* and Dijkstra shine.

[Septenary]

Thanks for all the quick replies!

I looked up the A* Algorithm before, but dismissed it because it seemed too advanced for my level, and possibly inapplicable to what I want to do. That page for beginners seems very useful though, so I'll attempt to understand it - thanks for the link.

Would it be a very expensive process if I were to use A* to path-find for several units (up to 10) on a screen at a time?

[ArmoredSandwich]

Thanks for all the quick replies!

I looked up the A* Algorithm before, but dismissed it because it seemed too advanced for my level, and possibly inapplicable to what I want to do. That page for beginners seems very useful though, so I'll attempt to understand it - thanks for the link.

Would it be a very expensive process if I were to use A* to path-find for several units (up to 10) on a screen at a time?

Depends on how you use it. In my game units only find a new path when they reached their target, as you can imagine that isn't really cpu expensive. If you seek a new path every frame.. well ya :P I have over 50 units riding around and there's no real fps decrease. Supply trucks and such do get stuck sometimes and it is a bit harder to drive around units and stuff. But, ah well, I guess it's what you prefer. Try the golden mid-way ;) .

Sirisian: Of course, A* isn't that hard when you know OOP for quite a while. But people who know that mostly do not create topics such as these... :S

[Jerryscript]

Here's a quick example from some code I'm working on. It assumes you have already determined the obstacle is in the path (see tonypa's vector tutorials), and assumes the pawn is moving up towards the goal. You can extend this to work in any direction (again see tonypa).
d1 = Math.sqrt( Math.pow(x1 - pawn._x, 2) + Math.pow(y2 - pawn._y, 2) );
if(goal._x > x1){
d1 += Math.sqrt( Math.pow(y1 - y2, 2) );
d1 += Math.sqrt( Math.pow(x1 - goal._x, 2) + Math.pow(y1 - goal._y, 2) );
}else{
d1 += Math.sqrt( Math.pow(x1 - goal._x, 2) + Math.pow(y2 - goal._y, 2) );
}

d2 = Math.sqrt( Math.pow(x2 - pawn._x, 2) + Math.pow(y2 - pawn._y, 2) );
if(goal._x < x2){
d2 += Math.sqrt( Math.pow(y1 - y2, 2) );
d2 += Math.sqrt( Math.pow(x2 - goal._x, 2) + Math.pow(y1 - goal._y, 2) );
}else{
d2 += Math.sqrt( Math.pow(x2 - goal._x, 2) + Math.pow(y2 - goal._y, 2) );
}
path.clear();
path.lineStyle(1,0xff0000);
path.moveTo(pawn._x, pawn._y);
if(d1 < d2){
path.lineTo(x1 - pawn._width / 2, y2 + pawn._height / 2);
if(goal._x > x1){ path.lineTo(x1 - pawn._width / 2, y1 - pawn._height / 2); }
path.lineTo(goal._x, goal._y);
}else{
path.lineTo(x2 + pawn._width / 2, y2 + pawn._height / 2);
if(goal._x < x2){ path.lineTo(x2 + pawn._width / 2, y1 - pawn._height / 2); }
path.lineTo(goal._x, goal._y);
}
Here's an example, without predetermined collision (which is why it always goes towards the obstacle): http://www.geocities.com/jerryscript1/shortpath.swf

[Septenary]

Thanks for the example, JerryScript! I don't quite understand though - it would only work when there is only one obstacle between the unit and the goal?

In using A*, I have encountered two problems - one, is that, as the unit is moving along the path determined by A*, other units would also be moving, and would probably eventually obscure the path that this unit is following. I would like to make it so that units do not overlap - but I think it would be unreliable and difficult to try and predict where a unit will be along their path when the path-finding unit gets there. To stop this, perhaps I could test if the unit is touching another unit - and if it is, recalculate a new path?

Another problem is that, if my map is split into a grid of say, 20x20 pixels, and a unit tries to find a path on that grid - the unit will not necessarily be 20x20 pixels large. So, when it is moving along the determined path, its excess size would overlap some unwalkable nodes. I guess I could do two things to stop this: I could create a new grid for each unit every time they need to find a path, and this grid would have nodes that are exactly as large as the unit - but this sounds a bit inefficient? Or, I could find a way to make it so that, when finding a path, if a node is too close to an unwalkable node (close enough that the unit would overlap the unwalkable node if it walked on the walkable one) make the node unwalkable. I'm leaning towards the first method, just because it sounds easier...

Sorry if these are stupid questions or imagined problems. Thank you for everyone's help! :D

[robotz]

I could create a new grid for each unit every time they need to find a path, and this grid would have nodes that are exactly as large as the unit - but this sounds a bit inefficient?

If every single unit in your game is a different size, then yes it would be quite inefficient - but if you can group them to similar sizes (at least as far as the collision boundary is concerned) then they can share grids. You'll often find in RTS style games (the old ones anyway) that while visually the units may not look identical, they do have the same collision boundaries when it comes to path-finding.

[Jerryscript]

My example only works for one obstacle at a time. You could do something as simple as hittesting for other obstacles along the way, and employ the same method to get around them. This would take care of your moving unit issue, and since you need to use some form of collision detection anyhow at the prior to using this method, it could be functionalized easily.

I only offered this as an alternative to A*, since A* is more robust than may be necessary in some games.