Find content
Not Telling
Firstly, if you don't know what pathfinding is, this script may not be for you.
If you do, then the first thing I would like to use to explain the script is the Dijkstra Algorithm.
Wiki: Dijkstra's Algorithm
I implemented the algorithm into a pathfinding function. It's very confusing to understand and I'm open to any tips to make it simpler or more efficient. I'm getting a headache just trying to think of a way to explain it, so here goes my best shot...
argument0: xstart. The x-location in our grid we start finding paths from
argument1: ystart. The y-location etc.
argument2: steps. The number of 'steps' away from the xstart and ystart we check.
This function reads from the variable from pathsteps[tile2[x,y]]. So tile2[x,y] is where you store the tile types of your pathing grid, and pathsteps[] is where you store how many 'steps' are used for that type of tile.
You need to set the two variables beforehand. So for example.
pathsteps[0]=1 //it costs one step to move over tile type 0.
pathsteps[1]=2 //it costs two steps to move over tile type 1.
for (a=0;a<64;a+=1)
{for (b=0;b<64;b+=1)
{tile2[a,b]=choose(0,1)}} //make our grid. Each tile is either type 0 or type 1.
w=64;h=64;(It also reads the variables w and h, the width and height of tile2.)The script stores data about each tile in the pathing grid. They are as follows.
distance[x,y]: The distance you would need to travel from the xstart and ystart. It takes into consideration how many 'steps' are used on each tile (from pathsteps[tile2[x,y]]). Initially very large so that the algorithm can minimize it.
visited[x,y]: This variable can be ignored, it is used to 'spread' the paths every loop. Initially false, unless its the xstart and ystart, then it is true (it spreads from the start).
previousx[x,y] or previousy[x,y]: The coordinates of the previous tile, according to 'this' tile. In other words, where you would come from to get to 'this' tile. Initially -1 for all tiles.
canmove[x,y]: simple true/false stating if the tile is more than argument2 away from the xstart and ystart. If the distance is less than argument2, its true. If not false. Initially false.
The variables __xshift and __yshift were at one time temp variables but are now used for finding a path.
//dijkstra(x,y,steps)
//variables required: tile2[x,y], w, h, pathsteps[z]
//var __xshift,__yshift;
//var visits,visitsprevious;
__xshift=argument0-argument2
__yshift=argument1-argument2
for (a=0;a<=argument2*2;a+=1)
{for (b=0;b<=argument2*2;b+=1)
{
if a+__xshift<0 or b+__yshift<0 or a+__xshift>w-1 or b+__yshift>h-1 {} else {
distance[a,b]=argument2+1
visited[a,b]=0
previousx[a,b]=-1
previousy[a,b]=-1
canmove[a,b]=0
spd[a,b]=pathsteps[tile2[__xshift+a,__yshift+b]]
}}}
visited[argument2,argument2]=1
distance[argument2,argument2]=0
stopper=0
visitsprevious=0
do
{visits=0;stopper+=1
for (a=1;a<argument2*2;a+=1)
{for (b=1;b<argument2*2;b+=1)
{if a+__xshift<0 or b+__yshift<0 or a+__xshift>w-1 or b+__yshift>h-1 {visits+=1} else {
if visited[a,b]=1
{visits+=1
if a+__xshift<w-1 {visited[a+1,b]=1;
if distance[a+1,b]>distance[a,b]+pathsteps[tile2[__xshift+a+1,__yshift+b]] {
previousx[a+1,b]=a;previousy[a+1,b]=b;distance[a+1,b]=distance[a,b]+pathsteps[tile2[__xshift+a+1,__yshift+b]]}}
if b+__yshift<h-1 {visited[a,b+1]=1;
if distance[a,b+1]>distance[a,b]+pathsteps[tile2[__xshift+a,__yshift+b+1]] {
previousx[a,b+1]=a;previousy[a,b+1]=b;distance[a,b+1]=distance[a,b]+pathsteps[tile2[__xshift+a,__yshift+b+1]]}}
if a+__xshift>0 {visited[a-1,b]=1;
if distance[a-1,b]>distance[a,b]+pathsteps[tile2[__xshift+a-1,__yshift+b]] {
previousx[a-1,b]=a;previousy[a-1,b]=b;distance[a-1,b]=distance[a,b]+pathsteps[tile2[__xshift+a-1,__yshift+b]]}}
if b+__yshift>0 {visited[a,b-1]=1
if distance[a,b-1]>distance[a,b]+pathsteps[tile2[__xshift+a,__yshift+b-1]] {
previousx[a,b-1]=a;previousy[a,b-1]=b;distance[a,b-1]=distance[a,b]+pathsteps[tile2[__xshift+a,__yshift+b-1]]}}
}
}}
}
visitsprevious2=visitsprevious
visitsprevious=visits
}
until (visitsprevious2=visitsprevious or stopper>300)
for (a=0;a<=argument2*2;a+=1)
{for (b=0;b<=argument2*2;b+=1)
{if a+__xshift<0 or b+__yshift<0 or a+__xshift>w-1 or b+__yshift>h-1 {} else {
if distance[a,b]<=argument2 {canmove[a,b]=1;instance_create((a+__xshift)*32,(b+__yshift)*32,o_canmovehere)} else {canmove[a,b]=0}}}}Translation of the code into english:
1. Go through our grid and store all the initial grid values.
2. Then set the values for the xstart and ystart.
3. Run through a loop that
(A:) checks the grid for 'visited' tiles.
(B:) If a visited tile is found, branch out to the left, above, right, and below, flag those tiles as visited, set their distance to 'this' tile's distance + that tile's number of steps, set that tile's previous x and y to 'this' tile's x and y. (B) is skipped if that tile's distance is already less than 'this' tile's distanc3 + that tile's number of steps.
(C:) checks how many tiles have been visited. If it is the same as the last check it stops the loop. (Also added a manual stopper to prevent an accidental infinite loop)
4. Goes through all the tiles and checks if their distance is less than argument2. If it is canmove[x,y] is set to 1. If not it stays 0.
The script checks if the tile that we are finding a path for is outside of tile2[x,y]'s limits (is negative or is over w or h). If it is it skips calculations for that tile.
It is very inefficient compared to A*. But it is an alternative. And with this pathfinding, not every tile has the same movement cost.
I know its very complicated and I will have an example up as soon as possible. If you have any questions before then feel free to post them.
