My*Star Algorithm

Exploring the complex world of A*Star I finally decided to write my own version, quite different from the original yet easy enough for me to understand.

My*Star -- written by dw817 (08-07-22)

What this program does is demonstrate the way I have found to solve a path from A to B. That is to find the smallest possible path in the least amount of time even if obstacles or walls are in the way.

To begin with, there is a common method previous to mine for finding the shortest path of point A to B even with obstacles in the way - it is called A*Star and is fairly complex as you can see:

https://en.wikipedia.org/wiki/A*_search_algorithm

Having examined this and watched many Youtube videos later on the subject, I just thought to myself, there has to be an easier way to do this. There must be !

Now what the classic A*Star algorithm does is determine the shortest distance between two points A and B, it also determines the distance for going in a possible direction to seek out B, using square root and exponents, and if it runs into a dead-end, it must backtrack, lock off that direction, follow its new thread of commands, and try a different path.

No easy feat to code.

But I would not have this. So I puzzled and puzzled till my puzzler was sore. And then thought surely it must have something to do with PAINT. I mean I wrote a paint routine years ago in Pico-8 and it touches all points except those that are blocked off.

So - I realized right then I COULD write a program that determines if its even possible to reach destination B from A - to ensure that it wasn't blocked off by a wall or other obstacle.

So I wrote that, and it worked. But then I thought, how can I make a path from A to B not really worrying about the distance for the moment ?

Well according to the original A*Star they check distances between points. So let me create a large 8x8 field for the screen and plot 2-digit numbers on the distance from there to the target, and - maybe follow the distances by going up by one each time.

While that worked pretty neat with no walls, once you added walls it quickly got stuck, and I was not sure of how to get around these.

So I gave it more thought. What if - what if I were to say point A is 1 and draw 2 around it and 3 around that, etc. Sort of like a multi-colored fill routine, giving a nice outline around the whole thing till it was done. In doing this I am not tracking the distance but where the seeker is at the moment of its iteration.

Well that certainly created an interesting display. Maybe then just follow the numbers from 1 to its end A to B ?

Yes, that works, but not all the time. If there was more than one path to reach point B my program would not guarantee to pick the shortest path each time, and it could also get stuck in a dead end. But I was getting closer to what I wanted.

So I thought again - how do I solve mazes ? Well, I CHEAT. :) That is if I really get stuck then instead I start from the END and work my way to the beginning.

So I reversed points, so the 1 started at point B and then I sent out my "paint" routine till it hit point "A" as there was no point in continuing to fill the screen once "A" was found.

And that looked better. The numbers were there. I didn't want to count backwards though so I added in the code to reverse the numbers recorded once target A was reached. So instead of from nn to 1 it was 1 to nn.

Then I took my finger and traced. I was closer but the tracking of the number was unpredictable when I did a diagonal movement.

And it's not like I ever wanted any diagonal movement in the grid-games I write anyways. So I changed my paint to not paint 8-tiles outward, but 4, the same as a player could move.

Well that worked and it certainly found the path but it took a terrible way to do it. Trailing all the way across horizontally in a straight-line and finally down.

Now while this was the same length as trailing manually with my finger, it didn't look right.

So I thought about it again. Why not do this ? Seek L R U D for if (x+y) mod 2 = 0 and U D L R if not.

The reason for the (x+y) means that it would automatically swap back and forth for every horizontal or vertical movement but not for diagonal, giving diagonal movement using only U D L R movements.

And that got it !

My*Star would now track in a neat diagonal line flipping from horizontal to vertical if the target was more easily reached that way.

And it worked. I could make 2 or more paths and because of the way my paint added numbers to the screen, it guaranteed the shortest path every time !

And there it is !

So after about a week of fighting this, I present to you my own offering for pathfinding, not AStar but MyStar, using my own method of pathfinding.

It may not be faster than A*Star but at least for me (and likely you) what I wrote is a lot easier to understand and follow.

Download the program HERE.

Be aware keys 🅾️ and ❎ can be pressed on an IBM-pc keyboard via the "Z" and "X" keys. Arrow keys are normal.

Once you have the program up and running, press a key to continue.

Then use LEFT ⬅️ and RIGHT ➡️ arrow keys to select a default wall and 🄰 and 🄱 arrangement. Or if you don't want one, just choose the first one seen here. Press 🅾️ to continue.

Now you can use the arrow keys to navigate. Move the cursor on top of the 🄰 or 🄱 block and press 🅾️ to lift it up. Then press 🅾️ to place it in the new location. You can only drop 🄰 or 🄱 on a blank tile, not a wall. To cancel the move and return the 🄰 or 🄱 block back to its original position, press ❎.

Press 🅾️ on a block or empty square to add or remove a block there.

When you are all set, press ❎ to initiate search for from 🄰 to 🄱. Hold down the 🅾️ key to run it faster. When complete you will return back to the map editor.

. . .

And that's it ! If you have any questions or suggestions, please let me know.