I was able to implement A* pathfinding over the weekend and this opened up a lot of functionality. My A* implementation was based on the following articles.
I used Eric’s articles for the A* algorithm main loop and data structures and Amit’s article to tweak my movement heuristics.
My first usage of the new pathfinding code was to write a “explorer”. My plan is to use this during dungeon exploration. The player can switch on “Auto Explore” and the explorer code will automatically explore the dungeon on the player’s behalf. It’s almost like running in Angband, but the code will only interrup when a monster or new item is detected.
My explorer uses a simple methodology for exploring the map. Pick the closest unseen tile, find a path to it (using A*) and then navigate there. Repeat until there are no more unseen tiles. This seems to work quite well.
At the moment this exploration algorithm is a bit “dumb” as the closest unseen tile isn’t always the best tile to pick. An improvement would be to give unseen tiles within the current room a higher priority than tiles outside a room (if the player was inside a room). This will cause the explorer to finish exploring rooms before heading out into tunnels.
My next usage of the explorer was to tweak my dungeon generation. As I generate a dungeon I let the explorer try and visit all the “walkable” tiles. If he can’t find a route to a specific unseen tile then the dungeon was generated with inaccessible areas.
My algorithm then switches to “Dig” mode. I find the closest seen tile (to the inaccessible unseen tile), find the path, and navigate to the seen tile. I then change my path finding behaviour to ignore all movement costs for walls (allowing it to move through walls) and to favour up, down, left and right directions over diagonals. A* now finds a path, through walls, to the unseen tile and my explorer now navigates to that tile. Everytime the explorer “bump’s” into a wall it creates a floor tile, forming a tunnel. My dungeons no longer have inaccessible areas.
The abibility to switch, replace or alter movement behaviour is quite important to me. I can now, independent of the type of actor (player, monster, type of monster) change the way it moves on the map. An “ethereal” movement behaviour would allow an actor to move through obstacles, a “digger” movement behaviour would allow the actor to dig tunnels through obstacles.
So far I’m quite happy with the results.
My next step is to implement some simple AI types that will “explore” the dungeon e.g. wandering monsters, follow the player, or guard an area.