10 Replies - 2314 Views - Last Post: 22 June 2012 - 09:25 AM Rate Topic: -----

#1 Nekroze  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 170
  • Joined: 08-May 11

MultiLayer 2d Path-finding?

Posted 21 June 2012 - 08:20 AM

I know how to perform path finding in a 2d environment with A* however I am trying to figure out an efficient way to do 2d path finding on a multilayer map.

By this i mean a 2d square map that has an x and y coordinates and some of these coordinates will have a path to the layer above, or bellow, which will be an entirely different 2d square map. This would be easy if every layer joining tile was reachable from one another however some will not.

To be clear a map will be similar to DwarfFortress, a flat 2d top down square map that has multiple layers with ways up and down to each layer.

For example to be able to move from one side of the map to another where there is a river in between the only available path(assuming no bridges) are to search for a path under the ground and through a tunnel and then up a layer back to the ground level and then from that exit to the other side of the river, the desired location to path find two.

I am not sure of any reasonable way to do this at all. Especially if the path requires you to go through more then one layer and or back again. Any ideas Dreamers?

This post has been edited by Nekroze: 21 June 2012 - 08:26 AM


Is This A Good Question/Topic? 0
  • +

Replies To: MultiLayer 2d Path-finding?

#2 Hezekiah  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 208
  • View blog
  • Posts: 552
  • Joined: 12-July 09

Re: MultiLayer 2d Path-finding?

Posted 22 June 2012 - 01:36 AM

The solution depends on how the layers are represented in your code. The basic idea would be to take the code which is run for each of the neighboring cells and repeat it for the cells above and below the current cell, if a path is available.

Edit: If you tell us how you store the layers, we can give you more specific details.

This post has been edited by Hezekiah: 22 June 2012 - 01:41 AM

Was This Post Helpful? 0
  • +
  • -

#3 Nekroze  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 170
  • Joined: 08-May 11

Re: MultiLayer 2d Path-finding?

Posted 22 June 2012 - 02:31 AM

The map at the moment is a 3d numpy array (python) of ints that corrospond to tile ID's.

I realise that i can make 2 sets of pathfinding grahs;
high resolution graph for each tile on a layer. There would be one of these for each layer.
low resoution graph that just contains each node that transits to another layer.

Doing this i can pathfind on the layers highres from the starting location towards the desired location, provided they are on the same layer otherwise skip this step. If no way can be found to the destination on the current layer then highres pathfind from the starting location the nearest transit point on the low resolution grid then pathfind through that layer from lowres transit point to lowres transit point until you get to the destination layer, then highres pathfind from the exit transit point to the destination, if it can reach the destiation you have a path otherwise go back and recurse through the transit point until it can find another way onto the desired layer and reapeat until completed.

This it seems has problems like 1 being rather slow and 2 would this not output the first path it found to the destination but not eactly the fastest way to the destination... For my game this isnt too much of a problem however if it can be more acurate for little cost then thats good.
Was This Post Helpful? 0
  • +
  • -

#4 Hezekiah  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 208
  • View blog
  • Posts: 552
  • Joined: 12-July 09

Re: MultiLayer 2d Path-finding?

Posted 22 June 2012 - 03:44 AM

The algorithm you are describing shouldn't be necessary. How do you store the directions in which you can travel from a cell (both horizontally and vertically)?

Edit: There isn't a big difference between 2D and 3D pathfinding. The physical shape of the graph differs, but the A* algorithm isn't affected by that. In the part of the algorithm where you loop through the adjacent cells, just make sure you loop through the cells above and below the current cell too (if they can be accessed from it). Your heuristic function should also take layers into account.

This post has been edited by Hezekiah: 22 June 2012 - 03:54 AM

Was This Post Helpful? 0
  • +
  • -

#5 Nekroze  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 170
  • Joined: 08-May 11

Re: MultiLayer 2d Path-finding?

Posted 22 June 2012 - 05:11 AM

I see what you mean, but wouldn't this mean that storing these graphs for repeated use would require a lot of memory as i would have to have every store a grid of each and every tile. My maps don't have door tiles or the like so i wouldn't know how to make a graph for it with less nodes.

Also as i have previously only used 2d path finding a bit i know that we need to know the distance to the destination, how is this accomplish in 3d though. In 2d its just a Pythagorean length of the destination x and y from the starting x and y position. How does it work with layers, do i do the same thing then multiply it by how many layers away from the start the destination is? If i do that then the cost of traversing to another layer would greatly increase causing the algorithm to check everywhere(well a lot of places) else on the layer before deciding to change layer right? isn't this slower because it checks more places?
Was This Post Helpful? 0
  • +
  • -

#6 Hezekiah  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 208
  • View blog
  • Posts: 552
  • Joined: 12-July 09

Re: MultiLayer 2d Path-finding?

Posted 22 June 2012 - 05:41 AM

I didn't say you have to store any extra information. I only asked how you currently determine from which cells you can move to which cells (including vertically).

The Pythagorean theorem in 3D is:
d^2 = x^2 + y^2 + z^2

Was This Post Helpful? 0
  • +
  • -

#7 Nekroze  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 170
  • Joined: 08-May 11

Re: MultiLayer 2d Path-finding?

Posted 22 June 2012 - 06:43 AM

Oh sorry i was responding on my phone, couldn't see your post so i got sidetracked and forgot. Yeah you move horizontally and vertically, as well as up and down a layer so long as there is a block in the given direction from the current block that is one layer up or one layer down. Also each tile has a Boolean type, Passable, that determines if you can go there ever.

The idea is that given a current tile, if a the tile to the left is not air then it is passable unless there is a tile above that tile to the left, if there is a tile above the tile to the left then you can traverse up a layer but only if that tile is passable and there is not another tile on top of that (ie a wall 2 layers high cannot be climbed but 1 layer can) if the tile to the left of the current tile is nothing (ie air) then it is not passable unless there is a tile to the left of the current tile and one layer down that is passable.
Repeat for horizontal and vertical from a top down 2d perspective.

This is run over each tile that isn't air on each layer, the check automatically skips the current tile it is graphing if it is not passable or if there is a tile at the same x and y coordinates one layer above it as there is no space between layers.
Was This Post Helpful? 0
  • +
  • -

#8 Hezekiah  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 208
  • View blog
  • Posts: 552
  • Joined: 12-July 09

Re: MultiLayer 2d Path-finding?

Posted 22 June 2012 - 07:53 AM

This is how I understand your current layout. Please correct me if I'm wrong.

Each cell is a cube, which is either air or solid. A cell is passable if it is air and the cell below it is solid.

To calculate to which cells a character can move:
def accessableCells(currentCell):
    for direction in [up, down, left, right]:
        adjacent = currentCell.cellInDirection(direction)
        if adjacent.passable:
            yield adjacent
        elif adjacent.type = air and adjacent.cellBelow().passable:
            yield adjacent.cellBelow()
        elif adjacent.type = solid and adjacent.cellAbove().passable:
            yield adjacent.cellAbove()


In the A* algorithm, you have to loop through the cells adjacent to the current cell. With the above function, that can be done like this:
for adjacentCell in accessableCells(currentCell):

Was This Post Helpful? 0
  • +
  • -

#9 Nekroze  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 170
  • Joined: 08-May 11

Re: MultiLayer 2d Path-finding?

Posted 22 June 2012 - 08:17 AM

very close, a air is not passable because you cannot stand on i, dirt for example is passable, lava is not passable nor is the "stone wall" tile or any wall tyle. basicly passable means it is a viable floor block. So each layer has floors and walls on it. A transit point is like a ramp that exists on the edge of a block where one side of it goes to a passable block on the layer beow and the other side of it goes to a passable tile on the current layer for example. if a transit point was expressed as a class or something it may look like this

class transitpoint:
    left = {"X": 5, "Y": 7, "Layer": 0}
    right = {"X": 6, "Y": 7, "Layer": 1}


There is a transit point there because 6x7x0 is a nonpassable non air block "a wal" but 6x7x0 is a passable floor block. if it was a wall then this would cease to work as a staircase and become more like a house wall.

Sorry if about my lack of ability to bring my point across and/or explain myself, i am not soo good at such.
EDIT: oh and thanks for the 3d pythag calculation.

This post has been edited by Nekroze: 22 June 2012 - 08:26 AM

Was This Post Helpful? 0
  • +
  • -

#10 Hezekiah  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 208
  • View blog
  • Posts: 552
  • Joined: 12-July 09

Re: MultiLayer 2d Path-finding?

Posted 22 June 2012 - 08:33 AM

Ok, so a cell can be either air, passable or notPassable. accessableCells() can then be rewritten as:
def accessableCells(currentCell):
    for direction in [up, down, left, right]:
        adjacent = currentCell.cellInDirection(direction)
        if adjacent.type = air:
            if adjacent.cellBelow().type = passable:
                yield adjacent
            elif adjacent.cellBelow().type = air and adjacent.cellBelow().cellBelow().type = passable:
                yield adjacent.cellBelow()
        elif adjacent.type = passable and adjacent.cellAbove().type = air:
            yield adjacent.cellAbove()


Note that this code assumes currentCell is the air cell the character is currently in. If you say currentCell is the passable cell the character is standing on, the logic will be slightly different.
Was This Post Helpful? 0
  • +
  • -

#11 Nekroze  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • Posts: 170
  • Joined: 08-May 11

Re: MultiLayer 2d Path-finding?

Posted 22 June 2012 - 09:25 AM

An air tile simply means that it is not able to be stood on in in layer it is in and that it has no graphical representation (void space) when drawing a map and an air tile is found it recurses down the layers on that x and y until a non air tile is found and draws that with a shadow to show it is below. passable is separate to the type. there is no real type a tile is just an ID that identifies it from the integers on a numpy array, the passable Boolean and an image which air doesn't have.

If it helps imagine a map of a large skyscraper. A map can be viewed by default with 0 slices. You see the roof of the building and the street around it. then you view the map with 1 slice, meaning it draws all bar the top most layer. So now you see the top floor of the building and everyone in it including its walls on that floor (a wall is a non passable block) and you still see the street around it. If you keep adding more slices you see the street outside and each layer going down towards the floor until you reach as many slices are above the ground layer. at this view slice you would see the street around the building and the lobby. for the first time you can see the people constantly as they walk from the street to the inside of the building, until they decide to go up a layer. one slice more down and you cannot see the street or building anymore (unless it has a basement) does that example help?

To be fair i think with the assistance you have provided so far i can work out a system to do this now so thank you. However i am worried that with the size of the maps that i want the graph that i have to store for the path finding may be a massive chunk of memory especial in python where using a dictionary of this size may be suicidal.

Problem is i need to have hundreds of npc moving everywhere between layers so it would be unreasonable to re-graph everywhere as they try and go to their destination, i would have to store it along side the map as i have done in the past (as a python dictionary) but that was only a 2d map of the same size as i want this time, with 10-20 layers... maybe cython can help to make a smaller graph to store in memory.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1