It’s Alive (almost)

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.

Path Finding Using A* in C# 3

Amit’s Game Programming – A* Heuristics

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.


2 thoughts on “It’s Alive (almost)

  1. HI !, Man u r cool !, i m just trying to be the same, i m walking in the same steps, A* algorithm, now trying to make explorer !, i made a good chasing behavior !, i ll try to use your idea a bout the closest unseen tile !, but i would like to ask u, how does the it works

  2. Ahmad, you’ll have to keep track of what your actor has seen and what he hasn’t.

    I do this with a visibility map for each actor. Basically it’s a 2D array (just like my terrain), but instead of the actual terrain types I keep track of IsVisible and WasSeen.

    To calculate the closest unseen location I ask my visibility map for all the locations where WasSeen is false. I then loop through all of them and calculate the distance between myself and each location.

    I use the following formula to approximate the distance between two points.

    Math.Max(Math.Abs(origin.X – destination.X), Math.Abs(origin.Y – destination.Y))

    I then select the closest unseen point, give it to my A* and ask it to calculate a path to this point.

    That’s my explore code in a nutshell. Let me know if you have any other questions.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s