Happion Labs GameDevBlog

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.

Speaking Engagement

I'll be in London next weekend (the 9th / 10th) speaking at this National Film Theatre thingy called NTI for Non Trivial Interaction, a movies-meets-games thing.  My talk, called "The Action Movie Aesthetic" will be a sort of games-meets-movies, games-loses-movies, games-buys-movies-flowers-and-gets-movies-back sort of deal.  Pretentious title, I know.  Sorry.  But I'm hoping to blow my last talk out of the water.  Thrills!  Adventure!  Fun for the whole family.  But it's PG-13.

More Thinking Aloud

Jason Della Rocca just mentioned modern portfolio theory.

(I should figure out what this trackback stuff is all about some day.)

Activision and EA mostly strategize by a different theory, which I've mentioned before:  tight / aggressive.

For the most part, they only back sure things.  And on those titles (hands?) they raise the stakes through the roof, spending insane amounts on development and marketing.

Which is why you and I are never going to get to play Dead Rush, the GTA-meets-zombies title that Treyarch was developing for a while before it got cancelled.  Or any of the other many titles you've heard of recently that sound interesting but aren't going to ship for one   reason or the other.  Which is sad.

But I have to admit, tight / aggressive seems like sound business.

Because breakout, out-of-nowhere hits like GTA and The Sims are incredibly rare.  Out of the dozens of cool new ideas that are developed each year, the bulk of them aren't profitable and only zero, one, or two of them might be the kind of stellar breakthrough that covers the losses of the rest of your company's failures.

Here's a question.  Maybe a team or studio is currently developing a wacky idea, that will be The Sims of 2008, if its funded and marketed to completion.  And maybe a publisher is thinking about pulling the plug on it.  You hear those rumors that The Sims was almost cancelled however many times.  Would that idea be lost forever?  Or...if the idea really is that great, won't it be able to survive in some form to eventually become the breakout hit it's destined to be?

I think the suckiest thing about risk-adverse publishers isn't that we won't get those breakout hits every n years.  The suckiest thing is that the not-quite-breakout ideas are lost.  The Dead Rushes of the world.  Because Dead Rush was a game I wanted to play.  I probably would have enjoyed it more than GTA.  But it wasn't going to be a GTA, not in terms of sales.

Batman Begins (the movie)

So we got a babysitter for the first time, just so I could see *Batman Begins*, and I guess it’s the best Batman movie made, but I was expecting more.  I think my main problem is this:  although it pays homage to the excellent *Batman:  Year One*, and though both Year One and Batman Begins are dark, Year One had heart. It had moments that got me, right in the sternum.  And that heart is missing from the movie.

Having some kind of momentous choice may be a Hollywood cliché, but it works.  Worked for Spider-Man and Superman and the X-Men.   And in *Year One*, Batman chooses to be Batman.  In *Batman Begins* it feels like he’s on a rail.  I suppose you could argue that in the movie he has to choose whether to be an executioner or not, but it’s not really much of a choice, it’s not like he’s really sacrificing anything.   In *Dark Knight*, for example, the choice to be an executioner or not is momentous.

And...that gives me a way to tie this into game development.  Choice isn't just important in games, it's important in fiction.  If the character seems to be on a rail, then the story is happening to the character, instead of the character making the story happen.

So what does that say about funhouse-ride games where the characters really are on rails?  Not only can we dis on their linearity from a game design point of view, we can dis on their lack of character development from a storytelling point of view.

On the other hand, some games, like KOTOR and Jedi Knight and Fable, give us the opportunity to explore the results of the choices the character makes.  But when we do, the story loses some of its power.  Like seeing the alternate ending for 28 Days Later, we become hyperaware that it's just a story.

I don't seem to have a point here.  Just thinking aloud.