a* algorithms (fun!)

[sotrain515]

Okay, I was about to hijack Mogri's Phantom Tactics thread but then thought better of it. Anyway, this is in response to James' post in that thread:

This reminds me that I really want A-star pathfinding and Dijkstra range-finding as built-in features. Your input Mogri, would be valuable as to how a plotscript interface for these should look.

I actually wrote a kludgy a* algorithm for my own game. It uses globals from.. I think around 1000 to 16000 to represent map tile costs (so I'm limited to 100 x 150 / 122 x 122 -tile maps but hey) and then it fans out from any given x, y coordinates using two for-loops (x, -range, range), (y, -range, range) and an if (abs(x) + abs(y) << range) and sets a cost for the given tile if it is adjacent to any cost-having tiles (it ignores 0-value tiles; the function starts off by writing a 1 at the given x, y). It then adds the range to the cost if the tile contains an npc or is otherwise an "obstructed tile". In that way, I created a situation where the enemies would go around obstructions if possible but would just bump up against them if not.

This took me several weeks to get working right for a few reasons. The first is that if you get to a range of, let's say around 50, the engine starts to chug (as you might imagine). To combat this, I have the algorithm dump out if it writes a tile next its target and the tile-cost it has written is less than the total range (still not sure if this logically makes 100% sense but in practice it seems to).. I also changed the direction the x and y for-loops fan out so that it will examine tiles that are closest to an "as-the-crow-flies" path first. Additionally, I have set up a waypoint system whereby there are waypoint npcs that attempt to cut off very large ranges; e.g. if hero x is above waypoint a and enemy y (the searcher) is below waypoint a, use waypoint a as the cutoff point rather than hero x.

Anyway, if I had my druthers, the plotscripting version would work like this:

First, there would be a function that would attach value to a range of maptiles fanning out from x, y arguments with a third arg being the range. An optional fourth argument would tell it how to behave if it found "obstructions" (and maybe another optional fifth arg that would determine what constitutes an obstruction, e.g. npcs and walls). The three behaviors I can think of are that it should either write a zero (valueless or "unreachable" tile), write a cost + range (as I have it doing above) or ignore the obstruction and just write the normal cost.

Next there would be functions like "get tile cost" and "set tile cost" to be run after the above function (args are x, y). And also a "get direction of lowest cost adjacent tile" and "highest cost" (args would be x, y again; I'd say "get coordinates" or "get tile" but I don't know how it would return that). These functions might also have an optional arg for it to determine behavior if two or more adjacent tiles are of equal value (e.g. "choose random", "choose bottom-leftmost", etc.). Also, there would be a "wipe out all costs" function, of course.


Okay, that was a lot of text... Please let me know if you have any questions or would like me to clarify. If you'd like to see any of this code I've described, too, just let me know.

Also, I'm not at all saying that this way is the best, please keep that in mind. Code optimization has always been a problem for me. If anything, I'm hoping that this thread sparks something of a dialogue on this subject (which fascinates me; I had never even heard of a* before about a month ago when I was doing Google searches for "path-finding for npcs"). I'll probably learn something!

[Mogri]

There are two use cases for pathing in Phantom Tactics. The more general one is unit movement range. Each unit can move up to N tiles, but the movement rules vary by unit: you can't move through enemy units, and Pirate units can cross water (as seen in the demo video; the Pirate class never shows up in battle during chapter 1). Since this is essentially what you and James are talking about, let's discuss the algorithm briefly.

Code: Select all

script, get move range, x, y, team = 0, range = 5, can swim = false, type = movetype:normal

The script is called recursively, but initially, you pass in the unit's current X/Y, its team, its movement range, and its movement abilities. The tile where the unit is currently located is given a value equal to range, then the script is called again with range - 1 for each of the surrounding tiles that isn't blocked (e.g. by a wall). This repeats until range = 0. If the script is ever called on a tile whose value is greater than or equal to range, then it aborts -- the tile has already been processed. If the tile's value is less than range, then it potentially needs to be processed again.

In an ideal algorithm, you would do the processing from highest to lowest range by using a priority queue. This would prevent you from ever needing to process the same tile twice. It's an optimization that I don't actually use here, since I never have a starting range higher than 9, but if I had to do it for larger sizes, then I would definitely have optimized it.

To answer James's question, a more general pathfinding function has several potential gotchas:

• Can I move through heroes?
• Can I move through NPCs?
• Can I move diagonally?
• If obstruction is disabled, should I respect that and move through walls/NPCs/whatever?
• Do I care about harm tiles? (The answer is yes -- if you have two equal paths, you should choose the one without the harm tile -- but how much do I care?)
• Do I need to account for changing conditions, such as an NPC moving into/out of my way? (Probably not -- this is the scripter's responsibility.)

For a general function, I'd expect an interface that looks something like this:

Code: Select all

find pathing cost(x, y, x2, y2, movetype, maybe some optional flags)

And possibly a helper function to determine the weight given to harm tile traversal. Movetype would determine whether you should respect walls, NPCs, and/or heroes as obstacles, probably with a tristate (yes/no/use current obstruction settings). Optional flags could include diagonal movement and such. The function would return some value that indicates how expensive it is to move from (x,y) to (x2,y2), or -1 if it's impossible. A second function:

Code: Select all

get pathing step(same parameters)

would return the direction of the next step to take in order to use the best path to the destination (again, with -1 for impossible paths). You'd need new constants for the diagonal directions. Sotrain's suggestion for adding specific tile costs is a good one, too.

The whole thing breaks down for use cases like Phantom Tactics, where you have movement rules that vary from NPC to NPC. Perhaps you could have yet another function to mark tiles as impassible.



The second use case for pathing in Phantom Tactics is for the AI, and I'll discuss that in the thread, since it's long and this is already long.

[Bob the Hamster]

Ah! So much good stuff here. I am glad to read all this, because it gives me perspectives on how these things might be used differently than I have experience with.

As for A* paths, I had been originally thinking about an interface something like this:

Code: Select all

p := find path(x1,y1, x2, y2, cost:default)
p := find path(x1,y1, x2, y2, @cost func)

cost:default would be a constant for a generic cost function based on walls, npcs, heroes, harmtiles, all respecting current suspendstuff state.

@cost func would be your own script that would get a par of tile positions, the tile being checked, and the tile that we are "coming from" and it would return a cost.

Since @cost func would likely be slower than the built-in costing, there could be an assortment of cost: constants for other built-in functions as needed.

The mention of diagonal movement means we would need something like:

Code: Select all

p := find path(x1,y1, x2, y2, cost:default, directions)

Where pathdirections is 4 or 8 (or something along those lines.)

Then of course, the cost function will actually need to know if we are pathing for a hero or an NPC, and which one, so it would be more like

Code: Select all

p := find hero path(who, x1,y1, x2, y2, cost:default, directions)
p := find npc path(ref, x1,y1, x2, y2, cost:default, directions)

And in most cases, the current location would usually be the current location, so we might want an argument order more like:

Code: Select all

p := find hero path(who, dest x, dest y, cost:default, directions, start x, start y)
p := find npc path(ref, dest x, dest y, cost:default, directions, start x, start y)

And actually, there is no reason to do away with the hero-npc agnostic version, so maybe all three of:

Code: Select all

p := find path(start x, start y, dest x, dest y, cost:default, directions)
p := find hero path(who, dest x, dest y, cost:default, directions, start x, start y)
p := find npc path(ref, dest x, dest y, cost:default, directions, start x, start y)

So then to actually use the path once you have it.

Code: Select all

for(i, 0, path length(p) -- 1) do(
  walk npc to x(ref, read path x(p, i))
  walk npc to y(ref, read path y(p, i))
  wait for npc(ref)
)

Or also

Code: Select all

for(i, 0, path length(p) -- 1) do(
  walk npc (ref, read path d(p, i), 1)
  wait for npc(ref)
)

And then when you are done:

Code: Select all

free path(p)

I think I would also make it that by default, unreleased paths get garbage-collected when you change maps, but maybe you could override that somehow:

Code: Select all

path persist on other maps(p, true)

Oh! yes, You reminded me about path failures. finding a path would always return a valid path handle, but there would be a command like:

Code: Select all

path succeeded(p)

That would tell you whether or not the path actually reached its destination tile. If the path failed, it will still contain the path to the tile that comes closest to the destination, but based on "if(path succeeded(p))" you can decide whether or not you want to use it.

Oh! And how could I forget:

Code: Select all

p := find path(start x, start y, dest x, dest y, cost:default, maxrange, directions)
p := find hero path(who, dest x, dest y, cost:default, maxrange, directions, start x, start y)
p := find npc path(ref, dest x, dest y, cost:default, maxrange, directions, start x, start y)

maxrange, so the pathing knows when to give up when searching for an unreachable destination. It would have some sensible default value, but I don't know what would be sensible :)

So that is just A*. Your Phantom Tactics AI gives me food for though about how Djikstra's range should work, although I guess am leaning towards a similar handle-based approach.

Code: Select all

variable(r)
r := find range(who, maxrange, cost:default, directions, start x, start y)

if(in range(r, x, y)) then(do something)

cost := read range cost(r, x, y)

free range(r)