The problems with pathfinders
Path finding can be an important part of many computer games. Unfortunately generating the nodes (points) used to find paths can often be very resource intensive.
Path finding in games can fall into two categories:
- Nodes are created when the level is created, usually manually and then saved into the level file
- Nodes are generated by the computer on level load, and possibly saved for the next time the level is loaded.
Recently i have been working on creating a program with python (using A* path finding) that can find the shortest possible route though a picture (.bmp or .gif) traveling only on white.
Some of my first versions of the program were extremely inefficient, generating many nodes that were inefficient and un-needed. It is not creating the nodes themselves that slows the program down but creating the links between them.
- Red dots are nodes
- Blue dots are nodes it has considered important
- Green lines are links between nodes
- The blue line is the final path
Version one of the program, it created all possible links between nodes, generating the path itself may not have taken long but to generate all the node links took over 2 minutes
My second version of the program attempted to select important nodes, the picture below shows the nodes it thinks are important
Success, it works much quicker than before with this maze being solved in about a minute
However it doesn't work for mazes that have allot of straight lines where the program ends up doing more tidying than it should, therefore making the maze unsolvable
The next version of the program tidys the nodes more quickly and also had a smaller grid size i found that for the program to run fastest, grid size should be less than a third of the width of the corridors, this new version managed to solve both the straight edged maze and the curvy maze, however it did a much better job at tidying the straight edged maze which took about 30 seconds to solve as opposed to just under a minute for the curvy one.
This was the most complex maze that i tested my program on and i got widely differing times depending on the grid size, by far the fastest was setting it to be the same as the corridor/wall thickness, however if it is slightly out it would probably fail, Solved as in the picture below it took about 30 seconds, or with a smaller grid size (less than a third of the corridor size) taking about 45 seconds
The program still has a few more tweaks to go before it is finished and then i plan on making some kind of demo game out of it.
If anybody has any ideas on node generation or a good way to tell witch nodes are important and which ones aren't leave a comment or send me an email