« Speaking Engagement | Main | Handheld Wars »

July 06, 2005

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.

Verify your Comment

Previewing your Comment

This is only a preview. Your comment has not yet been posted.

Working...
Your comment could not be posted. Error type:
Your comment has been posted. Post another comment

The letters and numbers you entered did not match the image. Please try again.

As a final step before posting your comment, enter the letters and numbers you see in the image below. This prevents automated programs from posting comments.

Having trouble reading this image? View an alternate.

Working...

Post a comment

Your Information

(Name is required. Email address will not be displayed with the comment.)

The Games

  • Energy Hook
    3D grappling-and-swinging-and-running-on-walls-and-doing-tricks ... with a jetpack ... for style!

Jamie's Bragging Rights

  • Spider-Man 2
    The best superhero games of all time Game Informer
    Top five games of all time Yahtzee Croshaw
    Top five superhero games of all time MSNBC
    Top 100 PS2 games of all time Official Playstation 2 Magazine
    1001 Games You Must Play Before You Die Nomination for Excellence in Gameplay Engineering Academy of Interactive Arts & Sciences
  • Schizoid
    Penny Arcade PAX 10 Award
    Nominated for XBLA Best Original Game
    Nominated for XBLA Best Co-Op Game