# Pathfinding between rooms

**URL:** <https://phaser.discourse.group/t/pathfinding-between-rooms/6334>\
**Category:** Phaser 3\
**Created:** [May 14, 2020, 2:28pm UTC](https://phaser.discourse.group/t/pathfinding-between-rooms/6334 "2020-05-14T14:28:17Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jeremy\_Lecler](https://yyz2.discourse-cdn.com/free1/user_avatar/phaser.discourse.group/jeremy_lecler/32/3166_2.png) [@Jeremy\_Lecler](https://phaser.discourse.group/u/Jeremy_Lecler)\
**Post date:** [May 14, 2020, 2:28pm UTC](https://phaser.discourse.group/t/pathfinding-between-rooms/6334/1 "2020-05-14T14:28:17Z")

</div>

Hello !

I would like to create a pathfinding system for my game.

The goal would be that when clicking in a room, the character is able to find the shortest way to get there.

Knowing that the number of parts and their arrangements is variable. The player can add where he wants and destroy it.

Knowing also that it only moves on an X axis. The only way to go up or down on the Y axis is to go through an “elevator” part (see the smallest parts on my image, 1x3 tiles)

Ultimately it can also wander in areas dug in the map (example: to the left of my image).

I have the ability to recover all the parts and their x / y position as well as to know if they are in contact with other parts and if so, know the side.

I watched a lot of tutorials but I never managed to find something that suited me. My elevator system is blocking me …

Do you have an idea to help me design such a system please?

I tried to trace path by making a loop on my pieces to see more clearly.

 ![Capture d’écran 2020-05-14 à 16.08.28](https://global.discourse-cdn.com/free1/uploads/phaser1/original/2X/3/3d9267e96faedb29d4a96c9163cd9b765243f476.jpeg)

```
this.scene.rooms.forEach( (room) => {
      this.points.push(room.x)
      this.points.push(room.y)
    })
this.validatePath()

  validatePath()
  {
    console.log(this.points)
    console.log(this.alreadyCheck)

    var curve = new Phaser.Curves.Spline(this.points);

    var graphics = this.scene.add.graphics().setDepth(50);

    graphics.lineStyle(1, 0xffffff, 0.5);

    curve.draw(graphics, 128);

    graphics.fillStyle(0x00ff00, 0.5);

    for (var i = 0; i < curve.points.length; i++)
    {
      graphics.fillCircle(curve.points[i].x, curve.points[i].y, 4);
    }
  }

```

Then I wanted to push the system starting from the room where the player is currently, making loops on the rooms with which it is collide.

The rendering is already more logical, but I know that I am still draft …

 ![Capture d’écran 2020-05-14 à 16.17.39](https://global.discourse-cdn.com/free1/uploads/phaser1/original/2X/d/dab68c45a4646241b310ab08bcbf0e55a169aef5.jpeg)

```
findPath()
  {
    this.onFindPath = true

    let startRoom = this.getRoomAtWorldXY(this.sprite.x, this.sprite.y)
    this.endRoom = this.getRoomAtWorldXY(this.scene.input.activePointer.worldX, this.scene.input.activePointer.worldY)

    this.points = [];
    this.alreadyCheck = []

    this.points.push(startRoom.x)
    this.points.push(startRoom.y)

    this.alreadyCheck.push(startRoom.sensor.id)
    // sensor.collideWithRooms = { left: xx/null, right: xx/null, top: xx/null; bottom: xx/null }
    Object.entries(startRoom.sensor.collideWithRooms).forEach(c => {
      this.checkRoom(c)
    })
  }

checkRoom(c)
  {
    if(c[0] == "left" || c[0] == "right")
    {
     // In the case of a normal room of 3x3 tiles. We can only go left or right
      this.getPathInRoom(c)
    }else if(c[1] && c[1].type == 'elevator' && (c[0] == 'top' || c[0] == 'bottom' || c[0] == 'left' || c[0] == 'right'))
    {
      // In the case of an elevator. The player can go in any direction. If he arrives in this room and has to go up, he will be teleported to the elevator room above it
      this.getPathInRoom(c)
    }
  }

getPathInRoom(c)
  {
    const room = c[1]

    if(room && this.alreadyCheck.indexOf(room.sensor.id) <= -1)
    {
      this.points.push(room.x)
      this.points.push(room.y)

      console.log(room)

      this.alreadyCheck.push(room.sensor.id)
      
      if(room.x == this.endRoom.x && room.y == this.endRoom.y)
      {
        this.validatePath()
      }else{
        Object.entries(room.sensor.collideWithRooms).forEach(c => {
          this.checkRoom(c)
        })
      }
    }
  }

```

I think that at first I need to create a grid with my rooms to be able to use it … But I have trouble visualizing how to create this …

I found this article which seems interesting to me, but I cannot adapt it: [http://gregtrowbridge.com/a-basic-pathfinding-algorithm/](http://gregtrowbridge.com/a-basic-pathfinding-algorithm/)

---

<div class="post-metadata">

**Author:** ![PBMCube](https://yyz2.discourse-cdn.com/free1/user_avatar/phaser.discourse.group/pbmcube/32/93_2.png) [@PBMCube](https://phaser.discourse.group/u/PBMCube)\
**Post date:** [May 14, 2020, 5:25pm UTC](https://phaser.discourse.group/t/pathfinding-between-rooms/6334/2 "2020-05-14T17:25:38Z")

</div>

Would this example help?  
[makingbrowsergames.com/starterkits/adventure/\_p3-2DRooms/index.html](http://makingbrowsergames.com/starterkits/adventure/_p3-2DRooms/index.html)

---

<div class="post-metadata">

**Author:** ![smjn](https://yyz2.discourse-cdn.com/free1/user_avatar/phaser.discourse.group/smjn/32/2087_2.png) [@smjn](https://phaser.discourse.group/u/smjn)\
**Post date:** [May 14, 2020, 5:42pm UTC](https://phaser.discourse.group/t/pathfinding-between-rooms/6334/3 "2020-05-14T17:42:45Z")

</div>

Perhaps you can base it on this?

> **[mikewesthad/navmesh](https://github.com/mikewesthad/navmesh)**
>
> A plugin for path-finding in JS using navmeshes, with wrappers for Phaser 3 and Phaser 2 - mikewesthad/navmesh

I’m using it and found it to be very nice. You have to do a little setup with creating all the navigation meshes (or write code to generate it), but otherwise straightforward usage.

---

<div class="post-metadata">

**Author:** ![Jeremy\_Lecler](https://yyz2.discourse-cdn.com/free1/user_avatar/phaser.discourse.group/jeremy_lecler/32/3166_2.png) [@Jeremy\_Lecler](https://phaser.discourse.group/u/Jeremy_Lecler)\
**Post date:** [May 14, 2020, 7:36pm UTC](https://phaser.discourse.group/t/pathfinding-between-rooms/6334/4 "2020-05-14T19:36:12Z")

</div>

From what I understood, it is necessary to draw rectangles with 4 points for each room?

```
const meshPolygonPoints = []
    this.scene.rooms.forEach( room => {
      let topLeft = { x: room.x - (room.width / 2), y: room.y - (room.height / 2)}
      let topRight = { x: room.x + (room.width / 2), y: room.y - (room.height / 2)}
      let bottomLeft = { x: room.x - (room.width / 2), y: room.y + (room.height / 2)}
      let bottomRight = { x: room.x + (room.width / 2), y: room.y + (room.height / 2)}

      let arr = [topLeft, topRight, bottomRight, bottomLeft]
      meshPolygonPoints.push(arr)
    })

    this.navMesh = new NavMesh(meshPolygonPoints);
   var path = this.navMesh.findPath({ x: this.sprite.x, y: this.sprite.y }, { x: this.scene.input.activePointer.worldX, y: this.scene.input.activePointer.worldY });

```

I saw that there was the Phaser plugin version, but it is based on a tilemap. I don’t think it’s useful to me right now, right?

---

<div class="post-metadata">

**Author:** ![Jeremy\_Lecler](https://yyz2.discourse-cdn.com/free1/user_avatar/phaser.discourse.group/jeremy_lecler/32/3166_2.png) [@Jeremy\_Lecler](https://phaser.discourse.group/u/Jeremy_Lecler)\
**Post date:** [May 15, 2020, 8:42am UTC](https://phaser.discourse.group/t/pathfinding-between-rooms/6334/5 "2020-05-15T08:42:22Z")

</div>

I did it!  
I have to find how to create internal margins in my areas (so that the points are right in the middle of the room, not on the edges). An idea ?

```
updateRooms()
  {
    const meshPolygonPoints = []
    this.scene.rooms.forEach( room => {
      let topLeft
      let topRight
      let bottomLeft
      let bottomRight
      
      if(room.type == 'elevator')
      {
        topLeft= { x: room.x - (room.width / 2), y: room.y - (room.height / 2)}
        topRight = { x: room.x + (room.width / 2), y: room.y - (room.height / 2)}
        bottomLeft = { x: room.x - (room.width / 2), y: room.y + (room.height / 2) + 10}
        bottomRight = { x: room.x + (room.width / 2), y: room.y + (room.height / 2) + 10}
      }else{
        topLeft = { x: room.x - (room.width / 2), y: room.y + 32}
        topRight = { x: room.x + (room.width / 2), y: room.y + 32}
        bottomLeft = { x: room.x - (room.width / 2), y: room.y + (room.height / 2) - 10}
        bottomRight = { x: room.x + (room.width / 2), y: room.y + (room.height / 2) - 10}
      }

      let arr = [topLeft, topRight, bottomRight, bottomLeft]
      meshPolygonPoints.push(arr)
    })

    if(this.navMesh)
    {
      this.navMesh.destroy()
      delete this.navMesh
    }

    this.navMesh = new NavMesh(meshPolygonPoints);
  }

  findPath(start, end)
  {
    let path = this.navMesh.findPath({ x: start.x, y: start.y }, { x: end.x, y: end.y });
    this.drawPath(path)
    return path
  }

```

 ![Capture d’écran 2020-05-15 à 10.40.43](https://global.discourse-cdn.com/free1/uploads/phaser1/original/2X/8/8f0db1c5cd88e3f51efb56b5fd7446f6aa7b237b.jpeg)

---

<div class="post-metadata">

**Author:** ![smjn](https://yyz2.discourse-cdn.com/free1/user_avatar/phaser.discourse.group/smjn/32/2087_2.png) [@smjn](https://phaser.discourse.group/u/smjn)\
**Post date:** [May 15, 2020, 7:15pm UTC](https://phaser.discourse.group/t/pathfinding-between-rooms/6334/6 "2020-05-15T19:15:37Z")

</div>

Nice!

You can get all the data about the polygons in the navMesh: this.navMesh.getPolygons();  
This might not be the fastest method, but I’m guessing from what I have seen/know of how you use it, it should be OK.

Do a findPath, check which polygons they are in by going over the list from getPolygons and fetch the centroid of each of those to make a new path. Maybe have to clean it up, as I think you might get double hits from the original path points being on edges, perhaps take the first hit for each point will be enough.

example:

```
    let path = this.navMesh.findPath(posA, posB);
    let navMeshPolys = this.navMesh.getPolygons(); //possibly it is this.navMesh.navMesh.getPolygons();
    let newPath = [];

    path.forEach(point => {
        //.some or other exiting loop instead will speed up
        navMeshPolys.forEach(poly => {
            if (poly.contains(point)) {
                newPath.push(poly.centroid);
            }
        });
    });

//Draw/return newPath
```

---

<div class="post-metadata">

**Author:** ![BryantFriend](https://yyz2.discourse-cdn.com/free1/user_avatar/phaser.discourse.group/bryantfriend/32/700_2.png) [@BryantFriend](https://phaser.discourse.group/u/BryantFriend)\
**Post date:** [May 21, 2020, 1:16pm UTC](https://phaser.discourse.group/t/pathfinding-between-rooms/6334/7 "2020-05-21T13:16:46Z")

</div>

I might be way off here but can you do a .setOrigin(0.5) ?