http://www.lastbossworks.com/Files/Pathfinding_distribution.zip
I'm finally following through on my promises to release this! I couldn't just release the pathfinding method; it relies on the rest of my engine. So the source I'm distributing now is a stripped-down version of SC2D, I've included just enough for the pathfinding to run. I'll release the rest sometime, but this is the meat of the engine!
Here's how the engine works:
Tilesets are defined in Open Game and look like this:
LET TESTTILES$ = "open block"
Where "open" and "block" are the names of sprites. That tileset will associate the open sprite with 0, and the block sprite with 1.
Tilemaps are defined as a string of numbers that represent tiles and a tileset that associates those numbers with sprites. A tilemap definition looks like this:
// define a test tile map
LET row1$ = "111111111111"
LET row2$ = "100000000001"
LET row3$ = "111100100101"
LET row4$ = "100010101001"
LET row5$ = "101000010001"
LET row6$ = "101010000001"
LET row7$ = "101001001001"
LET row8$ = "100100101001"
LET row9$ = "100000010001"
LET row10$ = "111111111111"
// to make a grid out of a tile map just add all the rows into one string
LET grid$ = row1$+row2$+row3$+row4$+row5$+row6$+row7$+row8$+row9$+row10$
// define map properties
LET tileheight = 45
LET tilewidth = 45
LET tilehh = tileheight/2
LET tilewh = tilewidth/2
LET MAP_W = 12
LET MAP_H = 10
// create the tilemap
// the grid| the tileset | i don't even | x| y|
TILEMAPMAKE grid$,TESTTILES$ , LEN(row1$), 49, 30
Ignore the tilehh and tilewh stuff, I forgot to take that out. The method TILEMAPMAKE takes a grid of tiles, the tileset, the length of a row of tiles (ignore that I don't remember why that's there), and the x and y coordinate of the top left tile on the screen, and displays the tilemap on-screen.
Parameters: gridd$,tileset$,rowlen,x,y
Pathfinding is achieved by two methods: BLA and FLOODPATH. BLA is a Bresenham's line algorithm implementation and is used to optimize the pathfinding in case a direct line from the starting to the ending position exists. Floodpath is a full-fledged pathfinding algorithm of my own design.
BLA takes the starting coordinates and the ending coordinates of a line, and attempts to cast a ray from startx, starty, to endx, endy, storing the coordinates of tiles intercepted by the ray in the arrays xlist() and ylist().
Parameters: startx, starty, endx, endy
FLOODPATH takes starting coordinates and ending coordinates and attempts to trace a path from startx, endx, to endx, endy, storing the coordinates of tiles in the path in the arrays xpath() and ypath().
Parameters: startx, starty, endx, endy
I've included an demonstration of how these methods can be used to move a sprite around a tilemap. The code for the demonstration is all in the Open Card and Mouse Down routines of card 1.
After defining and showing the tilemap, I define and create the player. The player is assigned the lowest open sprite number, x and y coordinates, and a move speed.
I ensure that the tile map is fully loaded, set a path iterator variable to store the player's location in his current path, and then start the main loop. Every iteration of the timer, I check to see if the player is at the end of his path. If he is not, I de-increment the path iterator and move the player to the next step on his path.
Whenever the player clicks the mouse, I find what tile the mouse is on. If the player has clicked an open tile, I check if a direct line exists from the player to the clicked tile - if so, I append the locations in that line to the path arrays and return. If not, I call the pathfinding algorithm to create a path from the player to the clicked location.
The pathfinding algorithm is really complicated, but I've commented it heavily. Rather than trying to turn the comments into a coherent explanation to put up here I'll let you guys read the source and ask me questions.
Yeah the paths aren't always the shortest, but they're always (as far as I've tested) correct.
And yeah, the directions that the pathfinder can check are defined in the beginning of FLOODPATH:
// these arrays store the directions in which the path finding algorithim checks for tile neighbors
// so theoretically for different AIs I can just change what directions are in here or add totally different stuff
// note - cutting out diagonal directions works. can use for different AI
DIM xdirection(8)
DIM ydirection(8)
// 1 = x+1, y+1
LET xdirection(1) = 1
LET ydirection(1) = 1
// 2 = x-1, y-1
LET xdirection(2) = -1
LET ydirection(2) = -1
// 3 = x+1, y-1
LET xdirection(3) = 1
LET ydirection(3) = -1
// 4 = x-1,y+1
LET xdirection(4) = -1
LET ydirection(4) = 1
// 5 = x+1, y
LET xdirection(5) = 1
// 6 = x-1,y
LET xdirection(6) = -1
// 7 = x, y+1
LET ydirection(7) = 1
// 8 = x, y-1
LET ydirection(8) = -1
So to make diagonals illegal you would just cut out the first four additions to the arrays and have
// 1 = x+1, y
LET xdirection(1) = 1
// 2 = x-1,y
LET xdirection(2) = -1
// 3 = x, y+1
LET ydirection(3) = 1
// 4 = x, y-1
LET ydirection(4) = -1