BFS Pathfinding algorithm using Javascript generator

Question

I'm implementing a BFS traversal in a grid-like structure. Because I wanted to experiment with ES6 Generators for a long time, I thought I'd implement the search using that abstraction.

I am sure there are obvious things I could improve in the code, because it looks fishy to me, especially after some "special constraints" that I needed to add.

Moreover, the code takes "forever" to run, and I was looking into any performance tips.

Background and constraints

1. What I am looking for is not really pathfinding, actually. I need to return an area for all the possible grid tiles an entity could reach.
2. Each entity has a certain movement range score.
3. Each entity has a certain action score. For every action point, the entity can move up to its entire movement range.
4. The boundaries between each range multiplier need to be clearly visible (so they must be returned in different groups, and can't just be added together).
5. Diagonal movement across the grid counts as 1.5, rather then the more classic Manhattan-distance 2.

Here are two images of what the result should be like:

1 action point 4 action points

As you can see in the first one, the green entity has 6 movement range and 1 action. In the second one, it is the same entity with 4 actions, the different shades show the different areas.

Implementation

Adjacent tiles

First of all, I've got two simple helper functions to get tiles which are adjacent or diagonal from a given tile. Perhaps I could implement these in some other way too, so feedback is accepted.

getTilesAdjacentTo(tile) {
 const cost = tile.cost || 0;
 return [
 { x: tile.x, y: tile.y + 1, cost: cost + 1 },
 { x: tile.x, y: tile.y - 1, cost: cost + 1 },
 { x: tile.x + 1, y: tile.y, cost: cost + 1 },
 { x: tile.x - 1, y: tile.y, cost: cost + 1 }
 ].filter(tile => {
 return (tile.x >= 0 && tile.x < this.size.x)
 && (tile.y >= 0 && tile.y < this.size.y)
 });
 }
 getTilesDiagonalTo(tile) {
 const cost = tile.cost || 0;
 return [
 { x: tile.x - 1, y: tile.y - 1, cost: cost + 1.5 },
 { x: tile.x - 1, y: tile.y + 1, cost: cost + 1.5 },
 { x: tile.x + 1, y: tile.y + 1, cost: cost + 1.5 },
 { x: tile.x + 1, y: tile.y - 1, cost: cost + 1.5 }
 ].filter(tile => {
 return (tile.x >= 0 && tile.x < this.size.x)
 && (tile.y >= 0 && tile.y < this.size.y)
 });
 }

It filters out tiles that are outside of the grid.

Search function

searchAroundTile: function* (tile, type = 'pathableOnly') {
 let costStep = 0,
 diagonalTiles = [],
 frontier = [tile],
 visitedTiles = [],
 currentTile;
 while(true) {
 // Get the first tile out of the frontier
 currentTile = frontier.shift();
 if(!currentTile)
 break;
 // I want to yield every time a circle of range 1 has been completed
 if(currentTile.cost <= costStep) {
 if(
 // Checking that the tile has not been visited yet.
 // Is there a better way not to add tiles that have been
 // visited to the frontier?
 !visitedTiles.some(
 tile => tile.x === currentTile.x && tile.y === currentTile.y
 )
 && (
 // Checks if the tile is pathable.
 // The first check is required because the tile with the
 // entity on it is technically not pathable.
 currentTile === tile
 || type === 'all'
 || this.isPathable(currentTile)
 )
 ) {
 frontier = [ ...frontier, ...this.getTilesAdjacentTo(currentTile) ];
 // I save diagonal tiles separately and concat them later so
 // that I can be sure that the frontier is kept in order of
 // cost, basically.
 diagonalTiles = [ ...diagonalTiles, ...this.getTilesDiagonalTo(currentTile) ];
 visitedTiles.push(currentTile);
 }
 }
 else {
 frontier.unshift(currentTile);
 frontier = [ ...frontier, ...diagonalTiles ];
 costStep += 1;
 yield visitedTiles;
 }
 if(!frontier.length)
 break;
 }
 yield visitedTiles;
 }

Calculate range function

calculateRange(from, range, min = 0, rangeType = 'all', repeat = 1) {
 let area = [],
 currentCost = 0,
 i = 1,
 search = this.searchAroundTile(
 { ...from, cost: 0 },
 rangeType
 ),
 visitedTiles;
 // This is in order to divide each repeat, but not to have to start 
 // a separate search from scratch. That's where I think the generator
 // pattern helps also.
 while(repeat) {
 visitedTiles = [];
 // Just iterate the generator until the cost of the last tile is in range.
 while(currentCost < range * i) {
 visitedTiles = search.next().value;
 currentCost = visitedTiles[visitedTiles.length - 1].cost;
 }
 area.push(visitedTiles.filter(
 // `min` is an optional argument in case one wants minimum ranges.
 // The second filter makes sure it removes from the current area
 // tiles that are not within that range. Sometimes I would end up
 // with a few tiles belonging to the previous area. This is 
 // probably a fault in the search algorithm which I didn't find. 
 tile => tile.cost >= min && tile.cost > range * (i - 1)
 ));
 i++;
 repeat--;
 }
 // `area` is an array of arrays, so it allows me to clearly identify
 // each area separately as seen in the picture above.
 return area;
 }

For what is worth, I have tried to quickly hack a non generator version of this code, and performance is the same. So the generator iteration doesn't really impact on the performance issue as far as I understand.

• juvian: 1) Your isVisited check is too inefficient. Use a 2 dimentional array to check in a single access if the grid is not too big, or use an object/set if its too big. Also don´t add all neighboring tiles when you visit one, add just the ones unvisited and inmediately mark them as visited. If not, you are adding the same tiles over and over before you visit them

Answer 1

Too many arrays

You have some poor array techniques that will be thrashing GC and adding additional processing load that can be avoided.

For example you add tiles to the array by recreating the array. That means that you need to keep both the old and new copies in memory and itterate over each tile when all you want to do is add 4 new tiles.

You add four tile using the following.

frontier = [ ...frontier, ...this.getTilesAdjacentTo(currentTile) ]

If you have 1000 tiles the above will need to store 1004 tile references (the original and the new 4) and iterate over all 1004. To complete the line you need to allocate space for double the array size 2008 tile references, for which half are dumped after the line is executed.

Much better can be done using

 frontier(...this.getTilesAdjacentTo(currentTile));

Now there is no GC hit and you need only iterate the 4 new tiles

Looking at the function getTilesAdjacentTo you create all four tiles that you hold in an array then you iterate them again, making a second array, that you return and immediately dump.

Keep it DRY

The functions getTilesAdjacentTo and getTilesDiagonalTo are almost identical and constitute repeated code.

Use one function and pass arguments that control diagonal or not and pass the array you want to add the tiles to so that you can add them directly.

Clear exit for loops

The main while loop in searchAroundTile has the loop exits inside the loop block, and are not required.

Modern JavaScript has a lot of optimization that happens as the code runs. When you create a loop that has no termination clause 'while(true)' some engines will mark the function that contains that loop as "DO NOT OPTIMIZE" Always provide a clear exit that the engine can deal with in the exit clause of any loop.

Your code looks something like

const frontier = [tile]
while(true) {
 currentTile = frontier.shift();
 if(!currentTile) // ref A
 break;
 // ... more code
 if(!frontier.length) // ref B
 break;
}

The statement at // ref A will never be true as the statement as // ref B ensures that.

You can remove the exit statements and just check the array length, removing 4 lines of unneeded code.

const frontier = [tile]
while(frontier.length) {
 currentTile = frontier.shift();
 // ... more code
}

Applying the above points the functions searchAroundTile, getTilesAdjacentTo and getTilesDiagonalTo can be changed to

searchAroundTile: function *(tile, type = 'pathableOnly') {
 const visitedTiles = [];
 const diagonalTiles = [];
 const frontier = [tile];
 var costStep = 0;
 var currentTile;
 while (frontier.length) {
 currentTile = frontier.shift();
 if (currentTile.cost <= costStep) {
 if (!visitedTiles.some(tile => tile.x === currentTile.x && tile.y === currentTile.y) && 
 (currentTile === tile || type === 'all' || this.isPathable(currentTile))) {
 this.getTilesAdjacentTo(frontier, currentTile);
 this.getTilesAdjacentTo(diagonalTiles, currentTile, true);
 visitedTiles.push(currentTile);
 }
 } else {
 frontier.unshift(currentTile);
 frontier.push(...diagonalTiles);
 costStep += 1;
 yield visitedTiles;
 }
 }
 yield visitedTiles;
},
// define the offset somewhere
const offsets = {down: [0, 1], up: [0,-1], ... and so on
getTilesAdjacentTo(arr, tile, diagonal = false) {
 const makeTile = (offsets) => {
 const x = tile.x + offsets[0], y = tile.y + offsets[1];
 if(x >= 0 && x < this.size.x && y >= 0 && y < this.size.y) { 
 arr.push({x, y, cost});
 }
 }
 const cost = (tile.cost || 0) + 1 + (diagonal ? 0.5 : 0);
 if(diagonal){
 makeTile(offsets.downLeft);
 makeTile(offsets.upLeft);
 makeTile(offsets.downRight);
 makeTile(offsets.upRight);
 }else{
 makeTile(offsets.down);
 makeTile(offsets.up);
 makeTile(offsets.right);
 makeTile(offsets.left);
 }
}

Visited tiles

You are using method Array.some to check for visited tiles. This is very inefficient. There two simple ways to change the CPU cost of each visited check from O(n), where n is the number of tiles, to n(1)

1. If the number of visited tiles is close to the total number of tiles. Use a array to mark visited tiles. Eg create array const visited= new Uint8Array(this.size.x * this.size.y); and then as a tile is visited mark the location visited[tile.x + tile.y * this.size.x] = 1; you then only need to check if(visited[tile.x + tile.y * this.size.x]) to know if you have visited that tile.

2. If the size of the map is very large an the number of tiles you visit small in comparison you can save some memory and use a Set to mark the visited tiles. EG create the set const visited = new Set(); and then add the unique index as you visit tiles visited.add(tile.x + tile.y * this.size.x); and to check you use if(visited.has(tile.x + tile.y * this.size.x)){

The search.

The function calculateRange does not feel right to me, but you have not provided enough context to check the logic against the abstract need. "Does not feel right" is not of much help to you so I will leave it as is.

• Sunyatasattva: Hey, thank you for your comment. All fair points! I especially face-palmed at my creating new Arrays instead of pushing. I guess I have that habit. Some other points I had already thought about in the meantime, cutting the performance hit by a bit. Since I did some refactoring on how the map is handled and now I have a matrix of all tiles, I was thinking of using Map instead of Set. I understand that the the unique values for Set is great, but, on the other hand, with Map I could add the cost and visited as metadata to the tile object without modifying it. Makes sense?
• Sunyatasattva: The context for calculateRange is explained above with the image. I need separate radii of tiles. It smells fishy to me to, and when I didn't have that need the code was way cleaner. Do you need any additional context? (I have upvoted, but perhaps going to wait to accept it until we discuss that part, if you have any feedback)
• Blindman67: @Sunyatasattva You can use Map or Set