I am using A* for pathfinding, and am creating a very limited graph to make traversal and pathfinding quick and easy.
How do I represent this as a data structure easily traversable from P0 to P1 by A* in python?
Everything is relative to points P0 and P1 which can be mirrored or 90 degree rotation to each other.
The points are at real coordinates and the other nodes are equal spaced and relative to our two points. The nodes have to remember their true coordinates so that once a path is chosen it can easily be drawn.
The weights on the edges are preweighted to give the resulting path an aesthetic look I prefer. The weights don't change so these can be pregenerated. However, there may be objects within the space that dynamically affect the weight of some edges (thus the need for pathfinding).
Pathfinding will happen every frame, so every 1/25th sec. So points for efficiency.
Here's the algorithm I'm trying to put together:
- Find the short and long side of the rectangle between the cells, work out the alignment.
- Calculate the coordinates of each node and edge.
- Apply pre-weight to the edges.
- Add additional weight for any nodes or edges that are blocked.
- Use A* algorithm to find the least-cost path which favors routes that minimize the distance.
And to remind you, a typical A* implementation has three user-serviceable parts I need to provide:
def move_cost(self, c1, c2, pred=None, start=None, goal=None):
""" Compute the cost of movement from one coordinate to another."""
def estimate(self, c1, c2):
""" Compute the cost of movement from one coordinate to
another. Often euclidian distance."""
def successors(self, c):
""" Compute the successors of coordinate 'c': all the
coordinates that can be reached by one step from 'c'."""
How do I generate and traverse this data structure?
