You are invited to Log in or Register a free Frihost Account!

# Determining the pathfinding algorithm being used?

Sylin
I am interested in knowing how to find out the pathfinding algorithm used in a certain game*.

It's a turn-based game played on a grid. Each unit takes turn making a move trying to eliminate the enemy.
There's a demo battle that anyone can play without having to register a game account here (uses flash). I am planning to use this to verify any conclusions we can make.

Here's my minotuar trying to move up but there's another minotuar in the way:

Here's the path it takes:

Now I replicate this configuration on a neat pathfinding demonstration tool I found:

Here's A* euclidean and Dijkstra respectively:

A* fits so I tried to verify a few more configurations when I found a problem:
Obstacle, or the lack thereof, near the path did not affect the path a unit takes in the game but it does in the pathfinding tool I used:
Now this is A*

And this is dijkstra

I am guessing that those blue and green squares are being calculated in a different order since having obstacle nearby means the algorithm can skip those. But then I don't know where to go from this point or even how complicated this may get :/

Do I have to start from the very fundamental and read up on this whole business of pathfinding algorithms? I am currently only aware of the names and a rough idea of how fast each one is, that's it
Or can I perhaps continue on with this trial and error hoping that it won't be too complex and at least try to be methodical about it like having a better dichotomy of the different configurations, etc.?

But to be honest, I am just a little lost at the moment :S
This turns out longer than I thought, so thank you for reading =)
Any help/ pointers are very welcome.

-- EDIT --

Pathfinding resources:
I think I'll need to go through these at some point.

More observations:
1. When choosing from more than one shortest paths, it tries to move orthogonally as far as possible before making any diagonal moves.
2. If there's a choice between moving upward and moving downward, it chooses up. If there's a choice between moving left and moving right, it chooses left.

1. and 2. are demonstrated here:

3. If there's a choice between moving up and moving left, it chooses left. If there's a choice between moving up and moving right, it choose up. Between left and down, it chooses left. Between right and down, it chooses down.

Combining 2. and 3., I arrive at the following priority list:
Left -> Up -> Down -> Right

Unfortunately, I couldn't replicate this behaviour in the pathfinding tool I posted above. I probably need to adjus some options here and there which I don't know anything about yet.

* Lords of War and Money, an online browser game based on Heroes of Might and Magic.

MODERATOR - Referral link altered. Referral links are not permitted on the forums; please read the Frihost forum rules to avoid future infractions.
- Ankhanu
I don't think you can know whether A* or Dijkstra is being used. Both algorithms are guaranteed to give optimal paths as long as the A* heuristic function doesn't over-estimates the remaining distance.

That you get different paths has probably to do with how paths of equal costs happen to be selected. This could be down to implementation details of the open set and the order in which the nodes are added to the open set. The open set could be implemented as a hash table, a binary tree, a heap or some other way, and there are many different variations of these that could affect what node is selected when more than one node has the same lowest cost.
Sylin
hmm, that means figuring out the full configurations is implausible right?

In that case, is it still possible to implement the movement based on observed patterns, most likely with configurations different from the actual one used by the game, but still conforming to most/all paths chosen by the game?

I haven't updated the original post yet, but by combining the 'basic' choices observed, I could pretty much tell the path the game will choose given a starting and ending point, at least I haven't found a counterexample yet. But I still need to look at the movement of the big 2x2 units like the green lizard though.

Thanks for your input, by the way
I am starting to look into computer science recently, so I don't know how those data structure works exactly yet.
Yeah, you could probably make something that mimics the game but it could be hard to verify that it's exactly the same in all situations.
Sylin
right, I see

Thanks for the help
Sylin
!!! I understand everything except the last bit of what you were saying in your first post now!!
Just need to look into the precise details of those data structures you mentioned in the end.
But yes, so mimicking the pathfinding behaviour boils down to the implementation details of the open set (assuming the game selects an optimal path).

I've also came up with the following heuristic which I think is admissible:

The rationale is provided by this diagram:

The heuristic is exact unless enough obstacle is there to force a minimum path to go outside of the rectangle formed by the 2 points, in which case the heuristic serves as a lowerbound.
SonLight
Ok, from your last post I see exactly how this relates to the standard Euclidian distance and what the rules of movement are. I want to comment on several notions of "distance" which need to be distinguished based on the context.

Notation: It is convenient to work with the x and y differences. They can be written as delta x or dx, for example. For convenience, I will define:

del x = abs(x1 - x0), del y = abs(y1 - y0)

Then Euclidian distance is sqrt( (del x)^2 + (del y)^2 ). This assumes freedom to move in any direction, and equal "cost" for movement in any direction.

In chess, for example, a diagonal move is considered equal in "cost" to an orthoganal move, so:

The distance in "Kings moves" is max( del x, del y)

In my notation, your formula would be:

abs( abs(del x) - abs(del y) ) + sqrt(2) * min( abs(del x), abs(del y) )

Possible extensions of the model include arbitrary directions, extra time to turn, having a limp or some other impediment favoring motion in certain manners or directions.

Of course, your first object should be to analyze the system you have. Possible generalizations usually are mentioned at the very end of a research paper.
Sylin
The heurisfic function d I've defined above is bounded above and below by the Manhattan and Euclidean metric, respectively.
This motivates me to look into whether d is a metric, on Z^2, say.
[del]I don't think it is, at least the first term is not positive definite, but I'll look at my algebra again and try out your delta notation.[/del] (the whole thing IS positive definite) but I got stuck manipulating the min{} function to get the triangle inequality right.

My goal of d was just to come up with an admissible heuristic that is as close to the actual distance as possible, and the unit in this game does in fact travel like the diagram above (they don't move freely as euclidean distance asks for).

As far as I know, a heuristic need not be a metric?
But yes, there are certainly areas to explore into, but within the scope of this game, I'd consider something like looking at the ways in which obstacles (if some of the squares are unavailable) affect the distance, or looking at the movement of large creature (unit that takes up 2x2 squares in the game map).
The whole purpose of this thread was to try and model the movement of this game here (link goes to demo battle from the game).