# Pathfinding trouble

This topic is 5150 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### Share on other sites
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.

##### Share on other sites
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]

##### Share on other sites
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.

##### Share on other sites
If your map is built by polygons, lines and vertices:
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.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by SuperNerdSee 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.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 11
• 15
• 21
• 26
• 11