Skip to main content

Pathfinding Experiment - 1

Demo program to test a pathfinding algorithm for a map with hexagonal tiles


Cary Semar
(lefty2000)
The problem of finding the best path between two points on a map which includes obstacles and roads is an interesting one. A good source is Introduction to A* at redblobgames.com. Another good introduction which I have found particularly helpful is at flashgamedojo.com. My goal here is to implement a path finding algorithm in python and to use pygame to provide visuals that allow watching the algorithm as it works its way over the map. The pathfinding algorithm I am using is not very efficient, but it is very thorough and will always find a solution if one exists. I cannot claim to have "invented" this algorithm; I worked out the details based on the descriptions of the various methods provided by the sources I have read, somewhat inattentively, so neither can I claim that it represents a correct implementation of any recognized method. Let's just say it is something I hacked together. The approach used is to calculate the weighted distance from the goal to every tile on the map. The weights assigned to a tile are based on the color pixel at the center of the hexagonal tile. The brown pixel indicates a road, the green is grass, and blue is water. Water is treated as impassable in this example. We want the actors on the map to behave intelligently, so we want them to follow the road when it makes sense to do so. The road tiles are assigned a movement cost of 1 and the grass tiles are assigned a movement cost of 3. More detailed information is available at my home page (see link) and there is a video showing how the algorithm searches the map to find the cost for each path to the goal.

Changes

Links

Home Page
http://www.lefty2000.com/Games/pathfinding/pathfinding.shtml
Source
http://www.lefty2000.com/Games/pathfinding/pfdemo_1.zip

Releases

Pathfinding Experiment 1 — 30 Dec, 2014

Pygame.org account Comments