sketch to demonstrate pathfinding, based on my old tile style maze generator. The optimal path isnt calculated, but that can be done with path pruning.
still to add image upload, and possibly connect it to neural network…
each tile has an opposite target tile. It seeks the shortest path, ive added methods for longest and other alternatives.
// find random unvisited cell
cell findNext(cell c){
//find longest path
cell findFurthest(cell c,cell b)
//find nearest diagonal
cell findNearestDGN(cell c,cell b){
//up down
cell findNearestUPDN(cell c,cell b)
left mousePress on sketch to add block tiles
right mousepress to activate pathfinding
ctrl+left mousePress to reset sketch
choose from 3 method calls
//
//find all predetermined opposites
findOpposite()
// find specific opposite 0-7
findOpposite(int n)
// parse through array ie [index 0, index4...]
findOpposite(int[] n)
now calculates nodes parents children and neighbours. Converts all cells with more than one neighbour to a node, its then possible to calculate optimal path. Find the first node in a cluster then the last node and repeat pathfinding until no more nodes, all cells have step size so an alternative is calculate max diff in a node cluster and find the one with the highest step value, the repeat pathfinding.
unlikely to be the most efficient, in the last one the bottom right finder finished before the top left and overwrote its color
Here’s one I wrote last night. This one is run on a 600x600 grid. Blue is water and pure white is mountain peaks both of which are uncrossable. Gray has a cost to cross it that increases with brightness. Moving diagonally costs 7/5 as much as moving left/right or up/down. Yellow is the optimal paths from a collection of starting points to the target red circle in the lower right.
Each cell only stores the cost to cross it, the optimal path direction (1 to 8, 0 means the cell is unvisited), and the path cost. The only other data structure is a priority queue implemented as a heap which has two arrays of integers, one for storing the heap and the other as a reverse mapping so I can track where a cell is in the heap.
The edges of the map are bordered in white so that I don’t have to check for boundary conditions. The code to find every optimal path to the target is
void findPaths( int endIdx ) {
int w = world.width, h = world.height;
dir = new int[ w*h ];
cost = new int[ w*h ];
q = new Queue( w*h );
dir[ endIdx ] = 9; // special "direction" for the end cell
cost[ endIdx ] = 0;
q.push( endIdx );
while( !q.isEmpty() ) {
int ic = q.pop();
for( int idir=0; idir<8; idir++ ) {
int oc = ic + neighbor[ idir ];
int ov = data[oc];
if( ov == 0 || ov == 255 ) continue;
if( dir[oc] == 0 ) {
dir[oc] = ((idir+4) % 8) + 1;
cost[oc] = cost[ic] + (((idir & 1) > 0) ? 7 : 5) * ov;
q.push(oc);
} else {
int newcost = cost[ic] + (((idir & 1) > 0) ? 7 : 5) * ov;
if( newcost < cost[oc] ) {
dir[oc] = ((idir+4) % 8) + 1;
cost[oc] = newcost;
q.moveup( oc );
}
}
}
}
}
neighbor[] is a quick lookup for indexing the neighboring cells by direction number. The dir[] array stores the direction number + 1 so that 0 can be used for “no direction yet known”. Direction 8 (or 9 in the dir[] array) is used for the end cell and so points to itself.
Total code is 288 lines. 80 of that is taken up by code that generates non-overlapping line segments that I didn’t use in the pictures above:
Each time you call findPaths() with whatever endpoint you want, it fills in the dir[] and cost[] arrays. You can then find the path from any cell by walking it following the dir[]s with a simple while loop. The paths should be reversible, so if you want to search multiple paths from you to multiple targets, you’d just use yourself as the endpoint.
Of course, you could define the path cost a variety of ways, some of which wouldn’t be reversible. For instance, it might make sense for travel to be cheaper when going slightly down hill vs up hill. I just used the assumption that low elevations are easier to cross than high and didn’t pay attention to slope.
This algorithm is a breadth-first search on a weighted graph. If the weights were just 1, such as in your examples, your queue can just be an array where you keep track of head and tail position. push() sticks a new cell on the end of the array and advances tail. pop() returns the cell at head and advances it 1. The order of the cells in the queue is fixed because the first time you see a cell, you’re on the shortest path to it.
If you look at my pictures, however, sometimes the best path starts by going away from the target. That means a cell behind that cell had a lower travel cost, so even though our cell might already be in the queue at some position, there is a cheaper way to reach it, so we need to move it forward in the queue by some amount. Also, when we add new cells to the queue, some will have much shorter costs than their neighbors and we want to visit the quickest-to-reach ones first, so the queue has to sort the cells as they are added to it. So, my queue is a priority queue implemented with a heap.
How do you want to use the paths in a neural net? What is the net trying to solve?
Here is a visualization of the travel costs to each pixel from a target near the upper left.
To answer your question about the pathfinder post, the neural network would be based on the variance and mean of the pathfinders 8 in total from their optimal travel path and their intersections, on a letter or number classifier or on a canny output, where only the outlines are left.
