Alright so I'm working on a snake AI that partially relies on A* for pathfinding, and I'm almost done, but I need help on calculating the difference between two coordinates.

For example, the potential new coordinate could be -3,6 and the goal coordinate could be 3,-6.
I need to determine the difference between these coordinates.
I know that, for this example, the difference is 6 and 12, but is there a universal equation I could use to calculate the difference no matter what the values are?
If all else fails, I could always just hard-code the 4 different equations, but that seems like a lot of unnecessary work.
Please let me know if there's another way.

Arbiter1227 wrote:

Alright so I'm working on a snake AI that partially relies on A* for pathfinding, and I'm almost done, but I need help on calculating the difference between two coordinates.

For example, the potential new coordinate could be -3,6 and the goal coordinate could be 3,-6.
I need to determine the difference between these coordinates.
I know that, for this example, the difference is 6 and 12, but is there a universal equation I could use to calculate the difference no matter what the values are?
If all else fails, I could always just hard-code the 4 different equations, but that seems like a lot of unnecessary work.
Please let me know if there's another way.

ok so say there is a 10x10 grid. if position 1 is (x1, y1) and pos 2 (x2, y2), then this formula should work.
|(x1-x2)|=distanceX
|(y1-y2)|=distanceY

if you don't already know | | means to take the absolute

Ok…

I Definitely Know what A* is!

*googles what A* is*

Ok. A* is a pathfinding algorithm, which finds the shortest possible path. (correct me if I'm wrong)

However, A* relies on the fact that the walls (snake body) to be stationary. But in the game snake, the walls will move, so A* will not work for a snake ai.

But there is another way. Hamiltonian paths.

Hamiltonian paths is a path which visits each vertex (space) exactly once.

A very simple snake AI is to generate a Hamiltonian path, and simply follow it.

I still need to do more research on how to generate a Hamiltonian path. Sorry

All of this is summarizing the video : https://www.youtube.com/watch?v=tjQIO1rqTBE&t=0s

NOTE: This video includes a LOT of swearing so watch at your own risk.


Hope this helps

Smanrocks wrote:

Arbiter1227 wrote:

Alright so I'm working on a snake AI that partially relies on A* for pathfinding, and I'm almost done, but I need help on calculating the difference between two coordinates.

For example, the potential new coordinate could be -3,6 and the goal coordinate could be 3,-6.
I need to determine the difference between these coordinates.
I know that, for this example, the difference is 6 and 12, but is there a universal equation I could use to calculate the difference no matter what the values are?
If all else fails, I could always just hard-code the 4 different equations, but that seems like a lot of unnecessary work.
Please let me know if there's another way.

ok so say there is a 10x10 grid. if position 1 is (x1, y1) and pos 2 (x2, y2), then this formula should work.
|(x1-x2)|=distanceX
|(y1-y2)|=distanceY

if you don't already know | | means to take the absolute

Thanks! I appreciate the help. I can't believe I didn't consider that.
Edit: This doesn't work when both integers are negative, but I can fix that with some minor if statements.
Edit 2: Nevermind, I'm an idiot.

27lucasl wrote:

Ok…

I Definitely Know what A* is!

*googles what A* is*

Ok. A* is a pathfinding algorithm, which finds the shortest possible path. (correct me if I'm wrong)

However, A* relies on the fact that the walls (snake body) to be stationary. But in the game snake, the walls will move, so A* will not work for a snake ai.

But there is another way. Hamiltonian paths.

Hamiltonian paths is a path which visits each vertex (space) exactly once.

A very simple snake AI is to generate a Hamiltonian path, and simply follow it.

I still need to do more research on how to generate a Hamiltonian path. Sorry

All of this is summarizing the video : https://www.youtube.com/watch?v=tjQIO1rqTBE&t=0s

NOTE: This video includes a LOT of swearing so watch at your own risk.


Hope this helps

Thank you, but I know that.
I already have a method for generating the Hamiltonian Cycle.
I just needed to tweak the A* system.

27lucasl wrote:

Ok…

I Definitely Know what A* is!

*googles what A* is*

Ok. A* is a pathfinding algorithm, which finds the shortest possible path. (correct me if I'm wrong)

However, A* relies on the fact that the walls (snake body) to be stationary. But in the game snake, the walls will move, so A* will not work for a snake ai.

But there is another way. Hamiltonian paths.

Hamiltonian paths is a path which visits each vertex (space) exactly once.

A very simple snake AI is to generate a Hamiltonian path, and simply follow it.

I still need to do more research on how to generate a Hamiltonian path. Sorry

All of this is summarizing the video : https://www.youtube.com/watch?v=tjQIO1rqTBE&t=0s

NOTE: This video includes a LOT of swearing so watch at your own risk.


Hope this helps

I apologize if my response came off as a bit rude.
What I meant to say is that the AI uses a Hamiltonian Cycle and A*.
Yes, it could use the Cycle entirely, but that would't really simulate an AI, since the snake wouldn't really head directly towards the food.

This is how I would do it:

First, we figure out where we are.
Then, we figure out where the walls are(snake body, edge(?))

Now 2 options
A. Continue using A*
B. Use another, simpler algorithm.

A.
We run A*, and record the next direction.

B.
We check the tile above us, and record its distance to the target. If it has a wall, we set its distance to Infinity.
The same for below us.
To the left of us.
To the right of us.

Now we record one step toward the direction with the lowest distance.

Use the output direction as the input for the game loop, then play out 1 game frame.

Wainggan wrote:

This is how I would do it:

First, we figure out where we are.
Then, we figure out where the walls are(snake body, edge(?))

Now 2 options
A. Continue using A*
B. Use another, simpler algorithm.

A.
We run A*, and record the next direction.

B.
We check the tile above us, and record its distance to the target. If it has a wall, we set its distance to Infinity.
The same for below us.
To the left of us.
To the right of us.

Now we record one step toward the direction with the lowest distance.

Use the output direction as the input for the game loop, then play out 1 game frame.

Thank you, but that won't work.
Even with a tweaked version of A*, it still needs to have a Hamiltonian Cycle for the endgame.