Pathfinding trouble
Author
I'm having trouble creating a pathfinding algorithm for my game.
The game is like civilization (with a bunch of squares laid out in a grid, each with a different movement cost). I'm trying to come up with an efficient algorithm that can compute the path between two squares that has the lowest movement cost.
I've already thought about defining some limits on the possible paths and then searching through all possible paths that fall within those limits. For example, I can compute a constant distance (in squares) that a path between two points can't deviate from. Then I thought about computing the movement cost of all paths that have a distance less than this constant and choosing the least costly one.
The problem with this, I believe, may be that it wouldn't run very efficiently on the computer. While I have read some of a book on C++ (Sroustrup-- the section on basic facilities and the chapter on classes) and have downloaded a free trial of C++ programing software (C++ builder), I haven't been able to program. I can't even get programs that I've transcribed from the book to work. Another thing is that I'm not sure what makes for more efficient and faster code. One idea I had was to create a loop through which each square (starting at the start point) would be assigned to an adjacent square until the route hit its distance limit or got to the end point. Another, probably much better, idea that I've just had and not thought at length about would be to load a set of squares into memory and somehow associate them with pointers. I've also read the C-part of a book by Deitel and Deitel that actually goes into uses of pointers, and I remember that pointers are used to make a program more efficient. What is it really that makes a program run faster or slower? I don't think my C++ book talks much about this.
If someone's willing to help, could they give pseudocode examples in addition to any in C++?
-- Scipio3
If you want to come from point A to B for example:
First draw the straight line between A and B, then you follow the line
until you come to an obsticle like a square for example,
then you follow the obstacles (the square's) edges til you encounter the straight line again to B.
First draw the straight line between A and B, then you follow the line
until you come to an obsticle like a square for example,
then you follow the obstacles (the square's) edges til you encounter the straight line again to B.
Hi Scipio3,
just to point you on the right path (Mmmwwwhahaha[lol]):
For your pathfinding questions, dig through ai-depot.com. Specifically, The Beginners Guide To Pathdfinding.
Pointers are useful because they a) can point to something, so you can create graph structures, and b) when you call functions, you can avoid the cost of copying large structures to the stack by using pointers, which are only 32 or 64 large.
For a better compiler, check out the Visual C++ 2003 Toolkit, the optimizing compiler from Visual Studio .NET 2003 (you will need an IDE, like Code::Blocks), or the Visual C++ 2005 Express Beta (additional installation instructions here).
Now I need a coffee. Just got up. [smile]
just to point you on the right path (Mmmwwwhahaha[lol]):
For your pathfinding questions, dig through ai-depot.com. Specifically, The Beginners Guide To Pathdfinding.
Pointers are useful because they a) can point to something, so you can create graph structures, and b) when you call functions, you can avoid the cost of copying large structures to the stack by using pointers, which are only 32 or 64 large.
For a better compiler, check out the Visual C++ 2003 Toolkit, the optimizing compiler from Visual Studio .NET 2003 (you will need an IDE, like Code::Blocks), or the Visual C++ 2005 Express Beta (additional installation instructions here).
Now I need a coffee. Just got up. [smile]
Some pointers:
1. At map creation time, identify all connex areas and number them. This way, if the object tries to move to a place it cannot reach, the search will immediately fail, leaving you with only possible moves to compute.
2. Use A* (A star) to determine the shortest path between your start and destination points. This algorithm uses the distance to the destination as a heuristic and adds it to the distance evaluation in Dijkstra's algorithm. Search the web for it, as it is a fairly documented algorithm.
3. Make the A* heuristic better by including, in each tile, the minimum time required to move two tiles in any direction from there.
4. Store, for planned paths, several waypoints along the path (the end position on each turn, for instance). This way, you can reconstruct each turn the shortest path to the next waypoint. You can also check for changes by recomputing the entire minimum distance (using the waypoints to shorten the search), and if it changed, recompute the path from scratch.
5. For AI moves when a lot of units will want to move to a given spot, do a reverse search to find the shortest path from the destination to all the units that want to get there by changing the heuristic every time you reach an unit. One search (although a little bit longer and requires re-sorting of a heap), several paths found at once.
1. At map creation time, identify all connex areas and number them. This way, if the object tries to move to a place it cannot reach, the search will immediately fail, leaving you with only possible moves to compute.
2. Use A* (A star) to determine the shortest path between your start and destination points. This algorithm uses the distance to the destination as a heuristic and adds it to the distance evaluation in Dijkstra's algorithm. Search the web for it, as it is a fairly documented algorithm.
3. Make the A* heuristic better by including, in each tile, the minimum time required to move two tiles in any direction from there.
4. Store, for planned paths, several waypoints along the path (the end position on each turn, for instance). This way, you can reconstruct each turn the shortest path to the next waypoint. You can also check for changes by recomputing the entire minimum distance (using the waypoints to shorten the search), and if it changed, recompute the path from scratch.
5. For AI moves when a lot of units will want to move to a given spot, do a reverse search to find the shortest path from the destination to all the units that want to get there by changing the heuristic every time you reach an unit. One search (although a little bit longer and requires re-sorting of a heap), several paths found at once.
If your map is built by polygons, lines and vertices:
To be continued when have more time.
struct Point { int x, y;};struct Vertex { Point position; Line **pLines; Uint8 nLines;};struct Line { Polygon *pPolys[2];};struct Polygon { bool walkable; Origin origin; SDL_Surface *pTexture;}struct Origin { Vertex *pVertex; int x, y;};Vertex *mapVertices;Unit16 numVertices;Line *mapLines;Uint16 numLines;Polygon *mapPolygons;Uint16 numPolygons;struct PathSegment { Point points(2);};struct Path { PathSegment *pSegments; Uint8 numSegments;};Path *BuildPath(Point *p0, Point *p1){}To be continued when have more time.
See of this would work for you. Pathfinding It finds the shortest path everytime. The only problem with it is trying to include moving obstacles.
Quote:Original post by SuperNerd
See of this would work for you. Pathfinding It finds the shortest path everytime. The only problem with it is trying to include moving obstacles.
There's also a version of A* that you can look up called RTA* (Real-time A*), which solves the moving obstacles problem, but has its own advantages and disadvantages as well.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
