Pathfinding between rooms

[Jeremy_Lecler]

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.

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 …

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/

[PBMCube]

Would this example help?
makingbrowsergames.com/starterkits/adventure/_p3-2DRooms/index.html

[smjn]

Perhaps you can base it on this?

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.

[Jeremy_Lecler]

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?

[Jeremy_Lecler]

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
  }

[smjn]

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

[BryantFriend]

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