Walls with several sides

[Franck728]

Hi. Is it possible to have walls with several sides ? That is to say that we can enter in the "square", but that we can only exit from certain sides. (See my drawing for explanations).
Thanks for help.

[brean]

Take a look at the getNeighbors function:
https://github.com/qiao/PathFinding.js/blob/master/src/core/Grid.js#L144
Instead of getting all neighbors this algorithm should only get you the ones that don't have a wall.
I would implement this with a second grid that stores the surrounding cells in binary, something like 11111111 (0xff) would be a completely cornered cell where all there are walls in all 8 neighboring cells. this way you could also relatively easy visualize it by assigning different graphics to each cell (0 for the empty cell 255 for the completely surrounded, and I would write something that creates these 256 images ;-) ).

[Franck728]

Hi Brean. Thanks for your answer.
I did not really understand everything. The relationship between the 2 grids (how ?), where to place the "binary infos" (array ?) ... I would need a little bit of concrete code to help me.
Otherwise, I found a solution that works perfectly well : divide each cell into nine "sub-cells" with a "wall" at each angle. But now, there is a big big big problem :
my original grid which makes 10 x 15 (150 cells), now makes : ... 30 x 45 (1350 cells) !
...not really good for performance.. :-) (See my drawing)

[brean]

My idea would be very similar to your sub-squares. you would just store the information of the 8 neighboring cells in a sub-cell not as own grid but as in binary, so you only need 8 bit to represent it. In the getNeighbors-function you would then extend the if for all directions, using the bitwise operators AND and right shift, something like this (assuming you store a blocking-value for each node):

    // ↑
    if ((node.blocking & 1) && this.isWalkableAt(x, y - 1)) {
        neighbors.push(nodes[y - 1][x]);
        s0 = true;
    }
    // →
    if (((node.blocking >> 1) & 1) && this.isWalkableAt(x + 1, y)) {
        neighbors.push(nodes[y][x + 1]);
        s1 = true;
    }
    // ↓
    if (((node.blocking >> 2) & 1) && this.isWalkableAt(x, y + 1)) {
        neighbors.push(nodes[y + 1][x]);
        s2 = true;
    }
    // ←
    if (((node.blocking >> 3) & 1) && this.isWalkableAt(x - 1, y)) {
        neighbors.push(nodes[y][x - 1]);
        s3 = true;
    }

and the same (node.blocking >> X & 1) for the edges, if you like to allow diagonal movement.

Note that I switched it up, 1111 would allow your path finder to go in all 4 directions while 0000 would block everything.

[brean]

Alternatively you could completely go with your solution and extend the getNeighbor-function to check the sub-cell and return only the center of the next cell if it is walkable, so for the path finding algorithm it looks like the same map as before (I prefere my solution which should be less memory-consuming but very similar to implement).

[Franck728]

Hi Brean. It works like a charm !
As I did not know how to proceed with "node.blocking", I used a second grid (as you suggest), with 16 possibilities of blocking (0-15) for each cell. So therefore, I have two grids:

• the "normal grid", named "matrix", with 0 as the default value for each cell (empty map).
• the "obstacle-value-grid", named "matrix2", with 15 (1111 in binary) as the default value for each cell (free cell !).

matrix = [
   [0,0,0,0,0],
   [0,0,0,0,0],
   [0,0,0,0,0],
   [0,0,0,0,0],
   [0,0,0,0,0]
]

matrix2 = [
   [15,15,15,15,15],
   [15,15,15,15,15],
   [15,15,15,15,15],
   [15,15,15,15,15],
   [15,15,15,15,15]
]

So, I coded according to your answer:

    if ((matrix2[x][y] & 1) && this.isWalkableAt(x, y - 1)) {
        neighbors.push(nodes[y - 1][x]);
        s0 = true;
    }
          // etc ...

Now, I have 16 possibilities of blocking inside a cell. This goes from the classic wall (0, [0000]), to the free cell (15, [1111])
(See my drawing).
By the way, I learned a lot from the "bitwise operators", which I didn't know.
Again, thank you very very much for your help !
Franck.

[brean]

Yeah, awesome work!

I would need to store this blocking value in the node somehow.
My first idea would be to put "special" values (maybe using negative numbers) in the original grid, but then it might get tricky if you want to use use it as a costmap or like to store different obstacle types. So I think in the end I would also use a second grid as well, should not really make a difference, so the second grid approach is a clean and flexible solution!