Search code examples
javascriptpath-finding

Find coordinates inside borders coordinates


I have x,y 4x5 dashboard. I have collisions array of objects which is:

const collisions = [{x: 1, y: 0}, {x: 2, y: 0}, {x: 0, y: 1}, {x: 0, y: 2}, {x: 1, y: 3}, {x: 2, y: 3}, {x: 3, y: 1}, {x: 3, y: 2}];

which basically make a square without edges. I also have array of destinations which is:

const destinations = [{x: 0, y: 0}, {x: 1, y: 1}, {x: 0, y: 4}];

the graphical representation is:

enter image description here

where red are collisions and gold are destinations.

I need algorithm which would find destinations which are surrounded by collisions. I can't walk diagonally so in above scenerio I want to find {x: 1, y:1}.

How to achieve it?


Solution

  • Instead of creating a new algorithm I would probably try to use well-tested established (and already implemented) path finding algos like A* (which is basically an optimized version of Dijkstra's algorithm, read more about path finding algos here) and adapt your scenario so these can be used. I think this approach will save you quite some time and make your code more reliable.

    Note that I converted your coordinate objects into arrays of coordinates, it is a) more common to express coordinates in this way and b) easier (and most likely faster => Arrays are fast) to work with them.

    For your example we basically want to find a path to each destination from some point OUTSIDE of your actual grid. We also need to make sure the destinations that are on the edge of your grid, e.g. [0,0] and [0,4] are reachable in some way, e.g. a path can lead to them. For this reason we expand/"pad" the grid with one node on each side. That means all your coordinates shift by 1 node.

    enter image description here

    From there we can simply check if a path exists to a destination. I'm checking from [0,0] which is now outside of your actual grid, but you can check from anywhere as long as the node is one of the "padding" nodes:

    const collisions = [[1, 0], [2, 0], [0, 1], [0, 2], [1, 3], [2, 3], [3, 1], [3, 2]];
    const destinations = [[0, 0], [1, 1], [0, 4]];
    
    // we expand the grid by one node on each side
    // otherwise destinations at the edge might not be reachable!
    const grid = new PF.Grid(4+2, 5+2);
    
    // set up the blocked nodes
    collisions.forEach(collision => {
    	// +1 accounts for the grid "padding" of one node
    	grid.setWalkableAt(collision[0]+1, collision[1]+1, false);
    });
    
    const paintGrid = grid => {
      const rects = [];
      const nodes = grid.nodes.flat();
      nodes.forEach(node => {
        rects.push(`
          <rect x="${node.x*24}" y="${node.y*24}" width="24" height="24" fill="${node.walkable ? '#FFF' : 'red'}" stroke="#000" stroke-opacity="0.2"></rect>
        `);
      });
      destinations.forEach(dest => {
        rects.push(`
          <rect x="${(dest[0]+1)*24}" y="${(dest[1]+1)*24}" width="24" height="24" fill="gold" stroke="#000" stroke-opacity="0.2"></rect>
        `);
      });
      document.querySelector('#grid').innerHTML = rects.join('');
    };
    
    const isTrapped = destination => {
    	// make a working copy of the grid
    	// as it will not be re-usable after processing
    	const g = grid.clone();
    	const finder = new PF.AStarFinder({
    		allowDiagonal: false
    	});
    	
    	// +1 accounts for the grid "padding" of one node
    	return finder.findPath(0, 0, destination[0]+1, destination[1]+1, g).length === 0;
    };
    
    paintGrid(grid);
    
    destinations.forEach(destination => {
    	console.log(`is ${destination} trapped?`, isTrapped(destination));
    });
    <script src="https://cdn.jsdelivr.net/gh/qiao/PathFinding.js@0.4.18/visual/lib/pathfinding-browser.min.js"></script>
    
    <svg id="grid" width="144" height="168" xmlns="http://www.w3.org/2000/svg">
    
    </svg>

    If you really need full blown path finding is of course depending on your real-world scenario, if your grid and destinations will always be that "small" in scale you could probably find an easier solution like the one suggested by @Yavuz Tas