next »

[st33d]

I'm doing a classic A* implementation, but the agent only needs to follow a path to a zone. (The agent is climbing up the side of a building with holes in and need to get to a given zone on the building.)

The obvious route I guess is to target the nearest edge of the zone. Any other thoughts on how I can tackle this?

Worth mentioning that CPU heavy tactics aren't good for this game, but I might be able to cache them or run them over several frames.

[Klaim]

Why not simply make your A* direction target the center of the zone and make it stop when it reaches a vertice inside the zone?


Another way to do this is to have another graph for "zones" only.

That way, you use this zone graph to know wich zones the agent have to go through. And inside each zone you'll have another path search to reach the exit of the zone to the next zone.
I've done this before, it works nice but you have to have entry and exit points in each zone (multiple or not).

[Dacke]

If you target the middle of the zone, you may not get A*. The heuristic in A* must be admissible: it may never overestimate the cost of reaching the goal.

But if you are aware of the risks, you will probably be just fine. Just try to keep the zones fairly compact.

If the heuristic aims for the nearest edge, you will get proper A*, though.

Edit: clarified some things.

[gwar]

I'm doing a classic A* implementation, but the agent only needs to follow a path to a zone. (The agent is climbing up the side of a building with holes in and need to get to a given zone on the building.)

The obvious route I guess is to target the nearest edge of the zone. Any other thoughts on how I can tackle this?

Worth mentioning that CPU heavy tactics aren't good for this game, but I might be able to cache them or run them over several frames.

I was wondering about this at yoga just now, why cant you return an incomplete path when you dont have any nodes in your open list?

[st33d]

My implementation allows you to do this by keeping track of the closest node during the course of the search.

http://github.com/st33d/red-rogue/blob/master/src/com/robotacid/ai/DungeonGraph.as

I love A* but I don't let the bugger choke my game when it can't find the absolute bestest route evar.

(Mind you I'm using a variation of that version for this current game I'm on.)

[Core Xii]

(this is assuming a "zone" is a group of "nodes")

Simple. As the heuristic, give it the distance to the closest node in the zone. Then it'll find the shortest path into the zone.

The real problem is speed consideration. The simplest approach is to iterate over all nodes in the zone and measure their distance, saving the lowest result. But if your zone is really, really big, that's a lot of checks, even if the distance calculation is simple. If you know more about the geometry of the zone, you could try optimizing this somehow.

[Klaim]

I think we don't have enough precision about how is structured your space and graph to really help you. All those answers are valid but it depends on what you already have. Is a zone a box in space? Is it a group of nodes? Are the nodes equally distant? etc.

[st33d]

The graph is top down. Four connections to each node. There are multiple maps that aren't static and mutate wildly (the agent is climbing a destructible building), so I've got a large empty graph that I start in the middle of and then as I search I check relative positions on the current map for legal nodes.

The zone is a rectangle of nodes. I've been trying the nearest node on the edge of the rect for now, it seems to work.

[nikki]

maybe have a light-weight search that has zones for nodes ?

[Dacke]

The zone is a rectangle of nodes. I've been trying the nearest node on the edge of the rect for now, it seems to work.

Should work perfectly, theoretically speaking. If the zone is a rectangle, it should be really inexpensive to find the best edge-node, too  

[Glaiel-Gamer]

If your graph is static, then precompute the optimal path to "target" nodes once at load time using Dijkstra's algorithm (i.e. A* without the heuristic), at this point knowing where to go at any given time is simply a matter of doing 1 lookup.

[Dacke]

there are multiple maps that aren't static and mutate wildly

[Glaiel-Gamer]

depending on how many agents you have, it COULD be more efficient to do it that way [every frame] still

[Zaphos]

If you target the middle of the zone, you may not get A*. The heuristic in A* must be admissible: it may never overestimate the cost of reaching the goal.

But if you are aware of the risks, you will probably be just fine. Just try to keep the zones fairly compact.

Fwiw I've seen "A* but with an inadmissable heuristic" suggested as a good approach -- see http://realtimecollisiondetection.net/blog/?p=56

The only risk is that you won't always get the optimal shortest path out -- but you'll still get some path, just biased in shape by the nature of your heuristic.  Since it's often not important to get the exact shortest path, it can be worth considering some inadmissible heuristics  and seeing if they can give you better performance, or even if you prefer the biased path.

Someone in the comments of that post linked to this:
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
Which gives a neat discussion of the different options for heuristics and how they can affect the results.

[Dacke]

Yup, that's what I said. You will probably be fine, if you know about the risks

But it won't be A* no more, though

[Zaphos]

Sure, but you should also know about the benefits

Re the name -- I would still call it A* ... I mean, it's a variant of the A algorithms, and that's what the name A* means -- the * is a regex-type symbol meaning 'all possible versions of A', isn't it?  Also, it's kind of a silly distinction, and the game industry generally seems to still call it A*.

[Dacke]

I would argue that it's important to keep the terms separated.

A* uses an admissible heuristic, by definition. This gives the algorithm some important properties. If you use a similar algorithm, but expect it to have the same properties as A*, you can get some nasty bugs.

Like this bug, that was posted here a few months ago. The algorithm sometimes chooses to use diagonals in strange places, due to an inadmissible heuristic (if I recall correctly):



But I agree that there is nothing wrong with using A*-approximations. I sure have!

[Zaphos]

Well ... of course one should be aware of whether a heuristic is admissible, and should be aware of the trade-offs in the choice of heuristic.  I don't see how either usage of the term A* really helps or hurts that though.

Use of an admissible heuristic just isn't part of the definition, really, or at least it didn't seem to be in the original paper defining the algorithm, and it isn't how people seem to use it in practice in the games industry.  (It even kind of misses the point of the name A* -- that it includes all variants of the heuristic ...)

[Dacke]

Admissibility is actually in the definition and in the original paper.

The paper starts by whining about the algorithms people were using at the time. How they either used mathematically based searches (which are admissible but don't take advantage of domain-specific knowledge). Or that people used heuristics, but without any guarantees that they would find the optimal path.

It then presents A*, under the heading "II An Admissible Searching Algorithm", followed by the proof of admissibility.

The important thing is:
If you are reading a paper that mentions A*, you must always assume that it is admissible (unless the text says something else). The theoretical properties of A* will not carry over to non-admissible versions.

• A* is guaranteed to find the optimal path
• A* is guaranteed to search the least amount of nodes possibly needed to find that path, given the heuristic at hand

[Zaphos]

Hmm, the original paper discusses using admissible and non-admissible heuristics for A* -- because A* is a class of algorithms, not a single algorithm (see especially Appendix B).  In the section you refer to, it defines A* generically for any h, and the admissibility condition is always kept as a separate additional condition on the admissibility of A*.  So, no, it's just not in the definition in the original paper.