July 2009

It was only a matter of time before I had to implement A* for pathfinding, but I recently read a post that opened my eyes a bit. The thread can be found here:

Over-engineering dungeon generation

Until today, I used to have a massive ConnectRooms function that connected different rooms. It would enter and leave rooms differently based on their type, and would kink around and bend in random locations. After reading this post I realized that my approach was horrible, and the results weren't that great. So I implemented A* and now I just make a call to A* to connect rooms. That's it ... one call ... well, mostly.

I made my A* algorithm flexible enough that I could specify whether I wanted to prefer straight lines, whether the path should follow the bee-line to the goal node. Now the dungeon generator just needs to keep its own pathing array as it draws rooms. The corners of rooms are marked as impossilble to pass, and the floors of the rooms are marked as easy to pass. The walls and the rest of the map are marked as hard to pass.

When I get a path back from A*, I draw the tunnel and update the pathing array to allow easy passage through the tunnels. Like the post states, A* starts to join up with other tunnels and rooms to get to the destination easier. This makes the map look cleaner, and the tunnels make sense.

My A* might need a little tweaking to get the best performance out of it, but I'm actually kind of glad that I allowed myself to just get it working at a good level and put it to use, instead of spending a week optimizing. I have to continually make myself do this, otherwise I get bogged down and don't see much progress.