How the pathing in my Tower Defense game works


Let's say we have the following map with the starting position marked “S” and the ending position marked “E”. The dark areas represent obstacles and the white areas are where you can move.



The first thing you need to do is create a list to hold numbers for all of the squares in your map. Leave the white areas blank and mark the black areas with a really high number. I'll use 99 in my example because the path won't get that high. But, in your code you may want to use 9999 or higher.

On the End position, mark that square with 0.



Starting on the lowest numbered square on the board, 0, go North one square and if it is not filled in, mark it with the next higher number, 1. From 0, go West one square and if it is not filled in, mark it with the next available number, 2. Repeat for South and East.



Now that you are done with square 0, go to square 1 and repeat the process.



Next, move on to square 2 and do it again.



Repeat this until the entire board is numbered.



In the Tower Defense game, this part runs in Turbo Mode and takes less than a second to complete.

At this point your map is ready for use.

Please note that if you get to the end of the map calculation routine and the square marked “S” is not assigned a number, the map is not solvable and therefore you must reject the last wall placed on the map.


Using the Map

Recall that we have a sprite located at the position marked “S”.



And, we have calculated a complete map.



If you'll notice the square marked “S” has a value of 25. We start with that value when determining which direction to go.

All you have to do is look North, South, East, and West from that point and look for the lowest number. In this case it is to the East and the value is 22.



Your sprite should then move to the square labeled “22” and repeat this process.



From square 22, looking North, South, East, and West, the lowest number is 20 to the East.

Your sprite simply needs to repeat this process until it is at the square marked 0.




Map Changes

That's great, but what if the map changes? No problem. The map calculation routine only needs to be run when the map changes. As I said above, that should take less than a second. Just pause all of the sprites until the recalculation happens. Then, the sprites need to look at the value of the square they're in and then calculate their next direction by looking North, South, East, and West.

Looking at our last map:



Imagine what would happen if your sprite was on the square marked “6” and the square marked “3” was suddenly changed to “99”, a wall. During the recalculation that happens, the new map may look like this:



Starting from what was “6” before the recalculation and is now “28” the sprite looks North, South, East, and West and chooses “27” as the lowest number and heads that direction.


Thanks for reading this far.

I hope this helps!

EDIT: By the way, this pathing algorithm is basically Dijkstra's Algorithm with all the distances set to 1. It was developed by the computer scientist Edsger Dijkstra in 1956 and first published in 1959.

User coolstuff had originally described this algorithm on the old message board. But, the message was lost during the move to 2.0.

I'm just redescribing it here for anyone who wants to know how pathing works.

His original pathing project can be found here: http://scratch.mit.edu/projects/1034493/

His script is so complicated you may not get much out of it. My Tower Defense project's script is in the stage and is called “Recalc Path”. It is fairly short so may be easier to understand.

An important thing to remember is that when you create the function to do the “Recalc Path” is to make it run in turbo mode. You can do that by creating a user-defined function and checking the “Run without screen refresh” option as shown here:



Hope this helps!

Awesomesauce!

Thankyou, I have always Wondered how this was accomplished

how would i use the pathfinding in here https://scratch.mit.edu/projects/107754268/

how would i use the pathfinding in here https://scratch.mit.edu/projects/107754268/

when backdrop switches to [ help...!v]
move (10) steps
wait (...) secs

Since this topic hasn't seen a new post from the topic owner in a long time, I'm going to assume that it is dead and close the topic. If it still is alive, the topic owner just needs to use the Report button to ask a mod to reopen it