Blobmap: an elegant alternative to a-star

So I've never actually implemented an a-star pathfinding algorithm.  I have done pathfinding - back when I was in college I wrote a computer version of Steve Jackson's *Melee* for the Mac;  it had a hex map and I worked on making it so orcs could find their way to you.  It was a hairy, horrible algorithm that involved raycasting and seeing if there was an obstacle and raycasting around that obstacle and recursing.  I mentioned what I was doing to Peter Akemann (who would later found Treyarch) and on the busride home from UCSD he sat with his head in his hands, thinking, and when we got back to the apartment he wrote an algorithm in about an hour that he called "blobmap".

The way blobmap worked is this:  you have a two-dimensional array that matches your map.  (Blobmap assumes your map is a two-dimensional array, and not an arbitrary network, which is one disadvantage it has over a-star.)  You do a flood-fill in this two-dimensional array, starting at the destination you're trying to reach.  You initialize the array to whatever the max value is for the data size you're using. You put a zero at the destination.  You surround that destination square with 1's.  And then you surround the 1's with 2's.  And the 2's with 3's.  Obstacles on the original map are left untouched in the array.  So the flood-fill will naturally go around walls and terrain.

Once you've filled the map - it's completely blobbed - your character can simply walk downhill to find the fastest route to the destination.  And you can do terrain costs with blobmap, too:  instead of incrementing by 1, increment by the terrain cost.

Is it as fast as a-star?  Probably not.  Is it more or less memory efficient?  I believe the a-star data will usually take more space than the array, but I'm not positive.  I'm not entirely sure how a-star works, to be honest with you.  And I'm not the only one:  I've talked to more than one programmer who knows how to implement a-star but doesn't actually totally grok the underlying details.  Which is one of the nice things about blobmap:  it's easy to understand.  The code is simple to read.  It is *elegant*.

We've used blob map on RPG's with tactical combat (Magic Candle 2, 3, 4) and we even used it on Die By The Sword - hashing our terrain polys into an array of sectors and then blobmapping through the sectors.

Then we heard about a-star and we used that on all our subsequent titles.  But I kind of miss blobmap.  And if I was doing an RTS or a tactical strategy game of some kind, where the terrain is a grid or a hex-map, I'd use blobmap first and only switch to a-star if I needed the performance boost.

Comments

[Rohan Verghese]

Unless your A* estimate heuristic is overly complex, I think it will always be better than this algorithm. Your blogmap algorithm is essentially breadth-first search, with the destination as the starting point and the initial point as the goal.

In the worst case scenario, A* will take exactly as much space and time as this algorithm (A* has one node and position for each space, just like this algorithm). However, A* will usually consider far fewer nodes, giving it an advantage in both space and time.

The best explanation I ever saw for A* goes something like this: Visualize the nodes being considered as a circle. In a breadth-first algorithm like your blogmap, the circle expands outward in all directions, until the edge of the circle reaches the goal.

A* is like that, but instead of a circle, visualize an oval, stretching only *towards* the goal. It's pretty reasonable to assume that the space covered by the oval is smaller, and that the edge of the oval gets to the goal faster.

Hmm. Not sure if that made sense. It's a lot easier to see with pictures.

[Rohan Verghese]

Heh. I kept calling it "blogmap", rather than "blobmap". I'll blame it on the subliminal influence of the title of this blog.

[Jeffool]

Rohan's right about A* being the most optimal so far as space. And it always finds the optimal path. Though it may not be the easiest to understand, and can sometimes take a while, which brings up the wonderful idea of pre-computed paths. Game Developer just wrapped up a six piece series on pathfinding on large maps and talks about a nifty idea I haven't toyed with yet, a pre-computed path planning method called "BHPA*" (Boundary Heiharchical Pathfinding A*).

This springs to mind a method that was actually used in a console platformer, though for the life of me I can't remember which. For every level a giant table was precomputed that held every possible path using the triangles of the world mesh. Each entry only held two bits. (Obviously, this allows four states.) The AI recognized three states as triangle corners to exit through to find his destination and a fourth state meaning he was at the destination. The enemy would look up which triangle of the world mesh he was on (say, 110), and which triangle he wanted to get to (140). The table would return "01" which tells him to exit the second corner of the triangle he was in, leading him to triangle "130". He then checked the table again with his new location and the same destination. Obviously not applicable in every situation as it can lead to odd paths depending on the world mesh, but still genius in my book.

[Sean Barrett]

If your "blobmap" algorithm keeps track of the leading edge that's being filled (keeps a list of the squares), this _is_ just breadth-first-search. And you guys were the ten millionth game programmer to rediscover it independently.

If instead you iterate over the whole map to put 2s next to 1s, then iterate over the whole map to put 3s next to 2s, congratulations, you invented just about the slowest algorithm possible, except if you tweak it properly you can actual make a single pass over the map each frame, and it slowly converges on the right answer, and if your pathfind target is moving (say, you're a monster chasing a guy), this will create an interesting compromise where information about how you move is slightly delayed. And if you have lots of monsters chasing the guy, they can all use this same pathfind map. (I'd originally intended to discuss some of this in the gdmag columns, but dealing with A* took way too long.)

I call the thing where you follow the breadth-first-search data backwards "gradient following", and as I mentioned in the aforementioned columns, A* lets you do the exact same gradient following, although most articles that talk about A* tell you to store the directions as you go and then look at those. This is necessary for general A*, but not tile-based A*.

Anyway, as to A* complexity, it's really not bad if you're keeping a queue for the front of your breadth-first-search anyway. More specifically, if your movement costs aren't constant--if different moves cost different amounts (and they probably do if you allow diagonal moves and try to make those at all realistic), you have to use a generalization of breadth-first-search known as Dijkstra's algorithm, which is just breadth-first-search with a priority queue instead of a regular queue. But once you've got the priority queue, A* is a pretty trivial change to add, and for simple distance metrics is going to be noticeably faster. See the gdmag columns for numbers comparing dijkstra to A*.

[GBGames]

QUOTE from Sean Barrett:
"If your "blobmap" algorithm keeps track of the leading edge that's being filled (keeps a list of the squares), this _is_ just breadth-first-search. And you guys were the ten millionth game programmer to rediscover it independently."

Luckily such an algorithm wasn't patented. B-)

[Cironian]

I can see one (possible) advantage with blobmap for some games though, namely that it allows you to utilize idle time when the player is still considering his options and hasnt picked a movement target yet. With A* you need to know the destination before you can start your calculations. With blobmap it doesnt matter at all since you are calculating movement costs and optimal paths for every possible destination anyway.

So, if your problem is that when the player finally clicks somewhere after a long time of thinking, and it takes too long for any movement to happen, this might be worth a shot.

Though in reality there is probably no such beast as "idle time" anyway, since every CPU cycle can be used to boost the frame rate of the graphics engine or something.

[Rohan Verghese]

Cironian: No, you're not doing that. The blobmap depends on the destination point. The blobmap describes a well (or topographic map), and the destination is the "deepest point in the well". If you pick another destination point, the shape of the "well" changes, changing the entire blobmap. You'd have to store a separate blobmap for every possible destination.

If you wanted do do something like this, precompute all the best paths, you would use probably something like Dijkstra's algorithm for each pair of points (or the Floyd-Warshall algorithm).

It's essentially the same problem faced by network routing protocols. From my node, find the best path to every other node. Take a look at the methods they use.

[Cironian]

Yeah, seems that I misread part of the original post, so what I had in mind had you starting from the start, not the destination.

Then you could fill each square with an accumulated movement cost (as in Blobmap) and a direction to the previous square in that path.

Once you pick a destination, you can just start there and follow the directional markers to grab your path.

Call it reverse blobmap... I am not claiming it is very efficient, just that it would work for pre-calculating paths and has a fixed memory cost. (Maybe a benefit for handheld device)

[Peter Dimov]

A* is a family of algorithms that differ by their heuristic function that estimates the distance to the goal.

Blobmap (breadth-first) is A* with this function set to zero.

[Patrick Hughes]

Having worked with Blobmaps before, I'll add my 2cents =D

Blobmap has several advantages over A* in various situations:

1) Given a static destination, generate one for the entire map and every mobile unit can use the same map to grind out a path no matter whence it sources.

2) Guaranteed processing time on constrained systems, for any size map you know in advance how long it will take to get all blobby with it.

2) Guaranteed memory usage for any given map, invariant over time.

3) It *can* be modified to work with a graph instead of a grid if you just think of it as an n-way grid.

4) When generation is complete you instantly know whether you can get to there from here, and with extra work of adding "what blocked this space" you can decode what obstacle to best bridge using the distance count as an heuristic.

5) The map can be generated in stages whenever there's idle time, spreading out the load on constrained systems.

6) It looks neat when debugged graphically =)

[Factory]

"No, you're not doing that. The blobmap depends on the destination point."
Well from JF's description of the algorithm it does, but if one was to start the flood fill from the source, as opposed to the destination it doesn't matter.
In a game like fire emblem for example, you have to do this regardless, so you can show the user what paths they can take on the map, so this ends up being a smarter algo.

[Jeffool]

Good points Patrick, but most of those instances seem to make me think that it'd be better as a precomputed path plan than an algorithm.

I still hold that for moving destinations it proves too costly to constantly re-evaluate. And even if it is static, it doesn't seem too useful to make a world-size blobmap during gameplay. Even if there is idle time during a game, there's always the chance that the very first move of the game will be to send a unit toward the to-be-blobbed destination. In that case you'll have to either use something aside from blobmapping to find it then, or blob the entire world first, and then allow the second move of the game.

Well, assuming it's not otherwise a computationally intensive game, it could work in those cases too. But if we're working with a static destination and resource space is no issue, then precomputing a blobmap makes great sense. Any method that is easy to visually comprehend and debug is a good method.

[PaG]

Talking about A*, one common misconception about it is that it's just a path-finding algorithm. It's not, it's a general problem solver for problems that can be represented as states.

Say you're coding the AI for a RTS. Assuming each unit as a ressource cost and a power level, the goal of the AI is to create an army with a given total power level using as few resources as possible. This problem could be considered as state-based by splitting everything in individual tasks: build this unit, then collect resources, then build a building to create further units, and so on. There's a very wide range of possible actions that can be done, but only one is the fastest way to reach the desired army power level.

In such a problem, you can use A* to search through all possible plans and choose the best one. In path-finding your states are individual locations in the map, in this case the states are current steps in a plan. This may not be the best example for using A* outside path-finding, but the algorithm can find the optimal solution for every kind of state-based problem.

---
Sacred cows make great steaks -- Fresh ideas on game development: http://www.pagtech.com

[TheOldShatterhand]

Are they still asking asking A* question on job interviews in Treyarch ? geez

[Jamie Fristrom]

Not since Pete & Don left. Also, I don't think it was an A* question, really, it was a pathfinding question. If you did a blobmap you'd get an A; and if you'd internalized A* you'd get an A+.

On blobmap vs. breadth-first: ok, so I guess these are pretty much the same thing, but I think with breadth-first you end up storing the same node in the map more than once in the tree, but with blobmap you've got a shorthand for making sure you only store each node's best path.

[Bacon]

Instead of A*, which looks like it's the optimal solution on paper, I like using the steering mechanisms of flocking algorithms for pathfinding. You get some nice group behaviours for free. And especially for animals and things, a steering and 'collision fields' (if you know what I mean) system looks sort of natural.