How do I check pathfinding availability across multiple regions?

  • Hi,

    So I have a theory on how to do this, but I'm not convinced it's the most efficient method. Basically, I want to have a top-down game where you can select units and move them around. However, I want there to be walls that block certain areas, and the units can't move into those areas until those walls are broken down. Now, this wouldn't be a problem usually, but one of the main features I want in this is a cover system, basically, you click on a unit and a series of available nodes pop up where you can place a unit, against said walls. If an area is blocked off, then no nodes should show up.

    So, my theory was to have an array set up that creates a cell for each grid on the world. Then, from a starting zone, have something like Easystar for Tilemaps run through a loop, testing each grid placement to see if there is a path available from the starting location, setting the array according to whether a spot can be reached or not. When a unit is clicked, the places that are available will pop up a node for the cover system, otherwise nothing is run.

    But, is there a better way to do this? Because the walls change, there will be certain events that will trigger a complete recalculation of available nodes, and I'm concerned that this will be expensive (ideally planning to have this running on phones). Even a small level of 50 x 50 cells would mean that 2500 paths would need to be calculated at the start of the level, and again every time a wall breaks, making me think that using this method will be too system intensive.

    I guess, now that I've typed this up, I realise I need a way to check a space next to a wall and only run pathfinding to those areas, rather than an entire array. Or even better yet, a system that spreads out from a single point (almost like water spreading out), and can return accessible routes. Is there a plugin that does something like this?

    I've included an image to better visualise this.

    Sorry for the slight stream of consciousness in that post, my thinking was changing as I typed, and I went with it. Plus my kids are playing ps4 so loud that it's hard to think :/

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • I once did a demo on terrain flooding, this is somewhat similar. Here is what I came up with:

    dropbox.com/s/yd0p2klipw3mccn/DungeonWallMarkers.capx

    This is probably not the best example and it needs to be optimized. I'm using Water tilemap to visualize "flooding" the dungeon and detect walls, you can use an array instead, it will likely work faster. Also, maybe call the function recursively for each neighboring cell, instead of looping through the entire array many times.

  • Cheers, I'll have a look at the capx.

    Think you're definitely right on testing cells based on their adjacent tiles, was actually thinking about that as I was driving home today. Should be able to cut out a lot of testing this way.

    Cheers

  • I guess the other option, which would be a lot more efficient, would be to click a unit, click on the tile to move to and, after pathfinding has been found and while the unit is in the process of moving to that spot, test if there are adjacent walls that can provide cover in that area and give the player the option to select the cover. So more of a two click system to get into cover.

    I actually think I might go this way.

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)