Simple path finding algorithm in assembler

[ParadigmShifter]

Oh I see what you mean now with values always being m + n * sqrt(2) that's the distance the agent moves yes (m orthogonal steps and n diagonal ones), but it isn't the "as the crow flies" Euclidean distance which is what I thought you were after.

I seem to be missing a beer though so I will go the shop and think about it a bit more

EDIT: Before I go the shop though I think that involves thinking about which octant you are in.

Look at this diagram and imagine the dotted lines but they are rotated 22.5 degrees (rotated both clockwise and widdershins so 8 dotted lines in the imagined picture). Which octant you are in tells you whether it's shortest to take mainly diagonal steps or mainly orthogonal ones

https://i.stack.imgur.com/Gk616.jpg

[Timmy]

I just wanted to make a quick post that I like people writing algorithms for pathfinding on the spectrum.

However, if I ever need one I'd write something on the spot, probably because it's fun to write one.

I'd also very likely use a regular floodfill and not A*, because I don't like how those A* paths look. But that's a personal preference.

Well done!

[ParadigmShifter]

A* and Flood Fill (Djikstra's algorithm basically) return the same path if the path to the solution is unique.

It depends on the order you visit nodes which path is returned if more than solution path exists that is the same length.

Even with flood fill you can get a choice of ways to go (same least cost nodes towards destination at a decision point).

You can add logic in to resolve ties like keep going forwards if you can, always turn clockwise, coinflip, etc.

Choice of ways to go with flood fill

Code: Select all

#####
#..G#
#.#.#
#S..#
#####

[ParadigmShifter]

I've got beer again now, phew.

Right, so have a look at this picture, angles in radians of course:



You want distances to be n + m * sqrt(2).

n+m = max(dx, dy) = total number of steps if there are no obstructions (steps either orthogonal or diagonal)

one of m or n will be min(dx, dy) the other will be n+m - min(dx, dy)

So if goal is at (2, 3) n+m is max(2,3) = 3. min(2, 3) = 2. So you take 2 steps either orthogonally or diagonally and 3-2 = 1 step diagonally or orthogonally.

(2, 3) is in a region nearer to the diagonal than the axis so you take more diagonal steps than orthonormal ones. So m = 2 and n = 1. So the distance in this metric is 1 + 2 * sqrt(2). EDIT: I keep getting m and n mixed up lol

Depending upon which region you are in depends whether you take more orthogonal steps than diagonal when calculating the distance. I've labelled some of the regions with whether you want n (which is number of orthogonal steps, nOrtho) to be bigger than m = nDiag steps.

There's an easy way to work out which octant you are in without doing any trig but I've not had enough beer yet It depends whether the goal is nearer to an axis than a diagonal...

[ParadigmShifter]

Who needs beer when you have wikipedia

Shortest distance to an axis from point (dx, dy) = min(|dx|, |dy|)

Distance from the line y = x (which is the line -x+y = 0) is

|dy-dx|/sqrt(2)

Distance from the line y = -x (which is x + y = 0) is

|dx + dy|/sqrt(2)

So for point (2, 3)

Distance to nearest axis is 2

Distance to line y = x is |3-2|/sqrt(2) = 1/sqrt(2)

Distance to the line y = -x is |2+3|/sqrt(2) = 5/sqrt(2)

1/sqrt(2) ~= 0.707 which is < 2 so we are nearer the diagonal. Therefore we want to take more diagonal steps than orthogonal.

I don't think the numbers 1 and 2 making an appearance (1 as the numerator in 1/sqrt(2)) in the distance of the nearest axis or diagonal is a coincidence either... not enough beer consumed yet.

https://en.wikipedia.org/wiki/Distance_ ... _to_a_line

checking distance to y = -x is correct

https://www.wolframalpha.com/input?i=di ... e+y+%3D+-x

[ParadigmShifter]

The only other thing you may want is a lookup of floor(n/sqrt(2)) where floor(x) is the largest integer less than or equal to x (i.e. INT x). Then you won't need to multiply by 1/sqrt(2) you can just look it up to find the value the axis distance has to be to be nearer than the diagonal.

Table can be very small, doesn't need to be the max extent of the map it's about half that/sqrt(2) I believe.

The code for a multiply function would be larger than the table size I think Also more accurate since 1/sqrt(2) is irrational of course. n/sqrt(2) is irrational unless n=0 of course. EDIT: So because of that, every integer lattice point which isn't the origin can never be equidistant to a diagonal and an axis, i.e. every point (a, b) with a, b integers except (0, 0) is unambiguously in exactly one of the 8 quadrants.

So that would be

index, floor(index/sqrt(2)), (value before floor taken shown in brackets)



Used the Speccy again lol

I couldn't work out how to tell WolframAlpha to print decimal approximation of 1/sqrt(2) instead of it showing in surd form

https://www.wolframalpha.com/input?i=ta ... %3D0+to+20

EDIT: I'd still have an option (conditional assembly) to use Chebyshev or Taxicab metric instead of doing something more complicated though.

EDIT2: If you want to store the distance though you still need a multiply by sqrt(2) function obvs Or you could use your 2 bytes instead to store nOrtho and nDiag and use the table to find out which is shorter. Or you could use a lookup of x -> x/sqrt(2) in some fixed point representation. You won't need the floor table then but it won't be 100% accurate cos of the irrationality of 1/sqrt(2).

Think I'm done for now anyway I do like a good bit of maths though interesting problem to solve You're halfway to discovering field extensions which are used to prove that there's no general formula involving nth roots for solving quintic or higher degree equations You've adjoined sqrt(2) to the rational numbers to make a field extension where members are of the form a + b sqrt(2) where a, b are rational

[ParadigmShifter]

Using what you currently have (sum of Chebyshev and Taxicab) is probably preferable to doing all that malarkey to work out which octant you are in though (EDIT: You don't need to know the octant you just need to know if you are nearer to a diagonal than an axis). It's a pretty good approximation (assumes sqrt(2) = 1.5, but it's not too bad and most grid-based games use that and no one notices) and your case showing it wasn't 100% correct is fairly contrived since as I said you'd need choke points which force you to pick one intermediate point on the path over another. I agree with your points about why just using Chebyshev or Taxicab can cause issues though. (Path too zigzag/path too all horizontal then all vertical).

I'd worry less about being 100% accurate and work on making the processing you do when working out the path more efficient... you should definitely look into implementing a minheap for a priority queue the code is not hard to write. That would make your deciding which node to visit first much more efficient I expect. (Although putting nodes in the queue is more complicated than just adding them to an array since you have to make sure the tree is a minheap at all times - so you can do about log N swaps where N is size of the heap. Log base 2 of course. Swapping pointers isn't very efficient either in Z80, but swapping entire elements isn't great either if they are 2 bytes or larger). Linear searching through an array to find the min value gets pretty inefficient pretty fast though (you have to check them all), so if you are currently doing that a lot, use a minheap instead is my advice.

EDIT: Working out the answer was fun though

EDIT2: And I think I've demonstrated how useful WolframAlpha is... great piece of software. You can operate it after beer o'clock and it nearly always gives you the correct answer, and you don't have to learn any complicated syntax you can just type obvious stuff and it usually interprets it correctly (I still can't work out how to get it to show 1/sqrt(2) as a decimal approximation in that table though lol).

[andydansby]

I know that I'm several days late on this subject with answers that are going to be superior to mine, but I would like to say that for my game F'n Balls, I used the Wavefront algorithm for my pathfinding needs. It ran quite quickly and took a nominal amount of memory to implement.

I write about it briefly at https://zxspectrumcoding.wordpress.com/ ... a-pathway/. I had a movement map that partially updated with each game pass. I would have to look at my source code, but I updated the map 1/3 of the time with each pass to reduce the time cost. Doing it this way the enemy that was further away would chase where you used to be, but the closer enemies would be dead on accurate.

edit: I also hacked up a quick windows demo with this function https://github.com/andydansby/wavefront. Perhaps it may be a bit useful to you.

[Einar Saukas]

I know that I'm several days late on this subject with answers that are going to be superior to mine, but I would like to say that for my game F'n Balls, I used the Wavefront algorithm for my pathfinding needs. It ran quite quickly and took a nominal amount of memory to implement.

I write about it briefly at https://zxspectrumcoding.wordpress.com/ ... a-pathway/.

That's how PATHFINDER works.

Except it uses a simple queue to avoid scanning the entire map at every step.

You can find a detailed explanation in the instruction files.

I had a movement map that partially updated with each game pass. I would have to look at my source code, but I updated the map 1/3 of the time with each pass to reduce the time cost.

PATHFINDER supports incremental execution too.

[sn3j]

I know that I'm several days late on this subject with answers that are going to be superior to mine, but I would like to say that for my game F'n Balls, I used the Wavefront algorithm for my pathfinding needs. It ran quite quickly and took a nominal amount of memory to implement.

I write about it briefly at https://zxspectrumcoding.wordpress.com/ ... a-pathway/. I had a movement map that partially updated with each game pass. I would have to look at my source code, but I updated the map 1/3 of the time with each pass to reduce the time cost. Doing it this way the enemy that was further away would chase where you used to be, but the closer enemies would be dead on accurate.

edit: I also hacked up a quick windows demo with this function https://github.com/andydansby/wavefront. Perhaps it may be a bit useful to you.

You're welcome to comment. The topic is always interesting.
I've read your article, much appreciated. I got a 404 on the link to the algorithm though.

If you are going to scan the whole array for the next wave you might run into performance issues with larger sizes.
My algorithm works with a cycling queue similar to Einar's solution. It's not designed for multi-pass yet.