Month: March 2014
I first learned about this algorithm when I was at school. I needed something to fill a maze with certain values and I was going for a brute-force flood-fill recursion when my teacher suggested I should use a wavefront.
So how does wavefront propagation work?
Suppose you want to fill a maze (or any connected graph) starting at a certain point in the maze. With a wavefront you:
- Mark that node in the maze – mark it with 1 as this is the first step in the wavefront propagation – then you insert it in the wavefront queue.
- Pick up a node from the “wavefront” queue (FIFO). Examine it’s wavefront value and make that current wavefront value.
- Examine all neighbours of the node in the graph. For any neighbours that are unobstructed and have not been visited yet: mark them with wavefront value + 1 and insert them in the wavefront queue.
- Repeat steps 2 – 4 until the wavefront queue is empty – i.e. no work left to do. All reachable nodes, that could be reached from the start, have been visited.
At this point you should have a maze that has been marked with wavefront values that represent the distance to travel to the start point. A distance field of sorts.
How is this useful?
1. Path-finding. Let’s say that we have two points in a maze – a start point and a destination. You can start a wavefront at the destination (yeah, it’s a bit backwards) and propagate it until the wavefront reaches the start point. After that “the path” is just following neighbours with decreasing wavefront values.
2. Distance map. Path finding is usually about finding the shortest path… using wavefront we can build a map of how far it is to travel to the destination at every node. That allows not only multiple agents to look-up and path find at zero cost (to the same destination) but also make decisions if they want to take a different path at any moment.
3. Multiple destinations. By slightly modifying the storage at each node we could have multiple destination wavefront values stored at each node – by storing an array of values instead of just single value. Then we can have hundreds or thousands of agents seemingly all efficiently path-finding towards their chosen destination while incurring 0 cost run time because it has all been encoded in the maze.
But what about the costs?
Wavefront has certain resource overheads. It has a queue that would grow up to the length of the current wavefront. And it would be more conservative than a heuristic based path-finding algorithm for example A*. Wavefront aimlessly fills the whole maze – it doesn’t target a certain destination.
These resource concerns can be addressed in various ways and quite often depend on the actual application. The two most often applications I go for are:
- pre-computation – using wavefront offline in a tool to compute the distance map and then save the data to use run time. This can also be in-game at level initialisation time. I used that in Carcophony
- time-distributed iteration – instead of propagating all wavefront completely on one go and fill the maze at once, I can do one node (or one wavefront value) at time… spreading the cost over multiple game frames. In Mazer I do exactly that – spread the cost over multiple frames.
How is this NOT useful?
Even though I like this algorithm, no doubt due to my early encounter with it, it can be very limited and grow complicated as we try to overcome it’s limitations. Arbitrary costs to traverse a node or node links for example… Carcophony had to deal with that as roads were of different length and not all neighbours are the same distance away.
Wavefront takes centre stage in my new game (codenamed Mazer for now). In that I try to make a game mechanic out of my nostalgia for a programming algorithm I learned very early on. I hope you grow to like it too.
A new game is in development…
I find algorithms and maths phenomena an interesting source of game design ideas.
A few years back that’s how BlindGiRl started. I wanted to make a game about wave propagation (using scalar field and integration on the GPU) and Fourier transform. Long story short, after couple of prototypes that project was parked only to come back in new clothes – GLPeas’ XBOX Live Indie Game – BlindGiRl.
This time around the inspiration is maze and path-finding algorithms. In particular wavefront propagation and A*.
Normally, these algorithms are just working in the background to aid the ever more complex AIs in a game do it’s job. AI programmers are working hard to make these more efficient and more realistic looking. In many cases good path finding systems are works of art.
In this game, however, the path finding algorithms are taking centre stage.
Code named Mazer for now, this has been something I’ve been working on and off for the last few months although it’s started to take shape only recently. It’s quite playable and if only there was more spare time it would be finished soon – plenty of work left though. Here’s a “work in progress” screen…
Enjoy and watch this space!