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

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