Rod-Mathisen

I am currently Global Executive Chairman of Notting Hill Games, a one-man part time games studio awaiting its first international blockbusting début. I intend to expose the sordid underbelly of the industry that is Amateur iPhone Game Development. A field, I am spectacularly unqualified to talk about, given that my only exposure is through a secret addiction to programming.
  • Find me:
  • Notting Hill Games
  • Posts in:
  • Advocacy
Posts by Rod-Mathisen
  1. Counting comments... )
Advocacy /

Once upon a time, there was a Prince who wanted to rescue his fair Maiden from the Evil Wizard. Now our gallant Prince was raring to go a-damsel-rescuing, but alas, there were many paths to the Evil Wizard's lair, how could he know which to take?

Well, our plucky wise royal just looked to the sky, for there he did see A*, to guide his way [ouch!].

For those not wincing I should add that A*, pronounced a-star, is the name of a path finding algorithm. Yes it is a terrible, terrible, pun. Sorry.

Path Finding For Princes

Well hello again dear Readers, I have bad news to report. Perhaps unsurprisingly, since I last wrote, I have utterly failed to do any sort of planning, scoping or other rational action to ensure I deliver my baby before my wife deliver hers. I have, however, had a lot of fun playing with path finding instead, so I thought I'd share it here.

A nice animation of A* in action from wikipedia - it can work a lot better than this.

Now, path finding is an old problem, largely considered a "http://www.ai-blog.net/archives/000152.html" target="_blank">solved" problem and therefore probably not that interesting to the various industry vet's who read/write here. So to those people, I recommend you just look at the pictures, you'll probably be appalled by the uneducated rubbish I'll be writing down.

To those of you who are completely unfamiliar with path finding algorithms, come closer my gullible friends. The principle is very simple:

  1. Build a list of Places-We-Know-How-To Get-To (let's just call them places)
  2. Add more places to this list by picking one place we already know, and see if it leads to any new places.
  3. Stop when we find a place that leads to our destination.

How good or otherwise the method is, largely depends on how we choose which place to consider for new leads, from the ones we already know. This magical part is defined by the algorithm used, of which there are many, but one of the best is A*, hence my awful joke at the start. I highly recommend checking out this Amit's excellent A* pages for much better descriptions than I could give.

All I will say about A*, is that firstly, it is a bit clever about picking the next place to consider, using both the distance it took to get to that place and a guess of how far it is from there to the destination. Secondly, it keeps track of places it has considered, so if it happens to re-consider a place, it will forget the worst way of getting there. Together these mean it will generally find a good path, relatively quickly.

To the rest of you, well, read on I guess.

The Scene

On stage is my baby, or at least the tender embryo of my iPhone game that is slowly gestating. It is to be a top-down, turn based strategy type affair, which I will say more about in future posts. For now, all you need to know, is that it will require "things" to navigate a set of relatively random, 2d maps. Breaking that down:

1. Things navigating will not be player controlled, but will move relatively slowly and with instant turning, so no need to worry about turning circles or the like. Their size will vary, but lets ignore that for today.

2. Navigate - things will have to figure out how to move from point A to point B, preferably along the shortest path, avoiding all walls and obstacles.

3. Relatively random - the maps and therefore the walls and obstacles are procedurally generated on demand, meaning that no manual input is allowed in making them navigable.

4. A set of maps - I'll be using lazy loading/creation in game time so there can't be a 1 minute pause while a map is analysed to create a navigation mesh or place waypoints.

5. Turn based - only one thing is navigating at a time, so the actual navigation part does not have to be that quick.

The Scenery

One way to make a map

So, my baby already has a few tricks up its sleeve. One of the first things I implemented was random dungeon generation. If you look over to the right you'll see how this works. It's very easy, has lot's of limitations, but does give you a random map.

The nice thing is that each of the wall's you remove effectively becomes a link between two areas. I tend to call these "exits" because when you are in an area, the exits are your path to other areas. Furthermore, if you ensure each area has a list of the exits available then path finding becomes very easy.

So with relatively little jiggery-pokery using this I had something that would use the exits and areas to find the best path across pretty much any map. Hooray. At this point I did the only sensible thing, got cocky and went utterly our of my depth. If only I'd listed to Han Solo...

The Acts

In a fit of enthusiasm, I thought that whilst having an infinite random dungeon is quite cool, what would be far cooler would be to allow the dungeon to have exits to the outside-world so that you could move between dungeons. In fact the random generation could be making oddly shaped houses rather than dungeons - et voila a random village!

In fact adding exits to the outside was easy, just add them to an area, but leave the other side of the connection attached to nothing - the outside. The issue was how to navigate outside. You see whilst "inside" consists of lots of areas we know the connections between, "outside" on the other hand, is just one giant amorphous blob. Sure we could link up every exit that is from an area to nothing, but what if we are trying to navigate from the outside to the outside, say from one side of a dungeon-cum-house to the other, how would it know whether to go around as opposed to through.

Part 1: Polyigonisation

Creating a mesh makes navigation easy, but creating the mesh is hard

The classical solution to this problem is to divide up the rest of the space into polygons, then replace the "walls" between them with exits. Almost as if we had added lots of interconnected room areas that happened to cover the entire map.

I've mocked this up on the right. Note that for this and the following diagrams, green things are supposed to denote places we know how to get to, while red denotes places we have considered. The route chosen will therefore always be along a red path of places considered.

In this case I hand crafted the polygons in a pretty haphazard way, however nonetheless they give a reasonable route with very few places being considered. The problem is, how would this polygonisation (yes, I made that word up) be done automatically.

Perhaps unsurprisingly, there are a bunch of algorithms to do this. Unsurprising because this type of navigational mesh appear to be used in lots of games, and I'm sure they don't hand craft them. However, these algorithms appeared, to me, to be (a) quite hard, and (b) quite processor intensive. They didn't look like the sort of operation that could be done on the fly by an iPhone. Which now I write it, makes me think I really ought to try it - a future post perhaps...

So what else could be tried

Part 2: The Grid

Another common solution is to forget the original area/exit based navigation and use a grid.

Using grid nodes - lots to check

In this scenario a grid is overlaid over the entire space and each point of the grid (the corners of the squares) is considered a node, I could have used the centre of the squares, but I prefer this way. So, let's call these points "grid nodes".

Movement then is done between adjacent grid nodes, either horizontally, vertically or diagonally, but criticaly, only one grid square at a time. Where the line between two grid nodes crosses a wall it is considered blocked and cannot be used.

The result is an algorithm that works a lot like the animated wikipedia image above. It doesn't mind about inside or outside, but it needs to check a lot more places and suffers a bit with rooms that are not aligned with the grid.

Comparing the number of places considered inside areas, to those by the mesh method, you can see why meshes are so popular; they cover more map with a lot less checking.

That said, it does generate effective routes. No, the real issue with this method is the number of nodes required to firstly be generated and secondly kept in memory. Again, I didn't fully implement this method, it just felt wrong to lose the efficient indoors navigation. A logical reason to progress if ever there was one!

So what next, well of course its time for...

The Finale - A Monstrous Hybrid

The best of both worlds?

At last, the point of this post, what did I actually do. Well in truth, I pretty much just mashed the grid and areas together into an awkward hybrid monstrosity. It worked as follows:

  • Whilst we are considering points inside an area will use the area's exits as our places-to-consider.
  • Whilst outside we will generate a grid on the fly, calculate which grid nodes are accessible and these as our places-to-consider.

Of course nothing is ever easy, in this case it is the transitions between inside and outside. The problem being that without further assistance a grid node will never go inside, whilst an exit will never go outside.

The solution is to build special cases for both situations:

When we are outside and considering a grid node, if one of the neighbouring grid nodes we are trying to reach is inside an area we do an extra couple of tests. First we find out if that area has any exits to outside - i.e. exits that connect the area to nothing. If it does we then test to see if our current grid node can get directly to that exit. If that is possible, then the exit is included in our open list of places we could visit, thereby allowing us to go inside.

Conversely, when we are inside, and are considering an area which has an exit to the outside - connected to nothing - we will identify all the neighbouring grid nodes to that exit. All the grid nodes that are not blocked will be added to the places we could visit, thereby allowing us to go outside. I've illustrated this below.

How to transition from inside to outside

The following animation was supposed to show how this would work in full, unfortunately I was a bit scuppered by the animated-gif-uploader limiting the number of frames to 10, so I had to skip a lot of stages. Hopefully it still shows the principle. Some points to note:

  • The crosses denote grid points that could become grid nodes as required, when they are called into play they become coloured:
    • The green crosses are places we can get to in one step (our open list in A* terminology)
    • The red crosses are places we have already considered (our closed list in A*)
  • The spokes are to show the neighbours of a grid point being considered:
    • The green spokes indicate a grid point we could navigate to
    • The red spokes indicate a grid point we can't navigate to
  • The final image shows the route after a little smoothing... clearly very useful in this circumstance and surprisingly easily done

The hybrid navigating Outside using the grid

Happily Ever After

So there you have it, the results of all my amateurish strivings - I have reinvented the wheel as a square, but at least our Prince can get to the Evil Wizards Lair; I feel strangely proud. Time will tell if this method survives play-testing, but even if it doesn't I have learned a lot implementing it. As ever, the beauty of amateur iPhone development.

But enough of this frivolity! Now, I really am going to knuckle down and get a plan together for this game I've pledged to deliver before 2011 is out.

Honestly.