Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  

Author Topic: Pathfinding question  (Read 975 times)

Duelmaster409

  • Bay Watcher
  • [DOES_NOT_FIGHT]
    • View Profile
Pathfinding question
« on: July 05, 2010, 06:59:57 pm »

I have a small little question; what happens if there are two or more paths to a certain location that have the exact same number of tiles in distance? Like so;

Code: [Select]
#########
#   @   #
#  ###  #
#  ###  #
##  +  ##
#########

Which path gets chosen? The left or right? We're assuming + is the start and @ is the finish, though it won't matter if they swap places.
« Last Edit: July 05, 2010, 07:02:45 pm by Duelmaster409 »
Logged
Dwarf fortress: Teaching uni level geology to sadistic elf killers for years.

Untelligent

  • Bay Watcher
  • I eat flesh!
    • View Profile
Re: Pathfinding question
« Reply #1 on: July 05, 2010, 07:21:42 pm »

Build a room like that, stick two doors that only open when a lever is pulled, drop a dwarf in there a whole bunch of times and find out.
Logged
The World Without Knifebear — A much safer world indeed.
regardless, the slime shooter will be completed, come hell or high water, which are both entirely plausible setbacks at this point.

tfaal

  • Bay Watcher
  • 'Ello, 'ello!
    • View Profile
Re: Pathfinding question
« Reply #2 on: July 05, 2010, 08:31:04 pm »

Alternatively, just build a structure like that into one of the hallways of your fortress, and see which way the dwarves go through; no levers needed.
Logged
I still think that the whole fortress should be flooded with magma the moment you try dividing by zero.
This could be a handy way of teaching preschool children mathematics.

Duelmaster409

  • Bay Watcher
  • [DOES_NOT_FIGHT]
    • View Profile
Re: Pathfinding question
« Reply #3 on: July 06, 2010, 12:24:25 pm »

Well if it was a hallway I'd just guess the side which has the least amount of traffic will get selected for use. It'll be tricky getting a dorf in the right spot when the door unlocks and he can go through.
Logged
Dwarf fortress: Teaching uni level geology to sadistic elf killers for years.

Urist Imiknorris

  • Bay Watcher
  • In the flesh, on the phone and in your account...
    • View Profile
Re: Pathfinding question
« Reply #4 on: July 06, 2010, 02:07:58 pm »

I would assume they would go left in your example. Dwarves have a tendency to want to go to the top left corner of the map.
Logged
Quote from: LordSlowpoke
I don't know how it works. It does.
Quote from: Jim Groovester
YOU CANT NOT HAVE SUSPECTS IN A GAME OF MAFIA

ITS THE WHOLE POINT OF THE GAME
Quote from: Cheeetar
If Tiruin redirected the lynch, then this means that, and... the Illuminati! Of course!

Captain Hammer

  • Bay Watcher
    • View Profile
Re: Pathfinding question
« Reply #5 on: July 06, 2010, 02:17:07 pm »

Build a room like that, stick two doors that only open when a lever is pulled, drop a dwarf in there a whole bunch of times and find out.
Spoken like a true dwarven scientist. Just add magma and you got yourself an experiment!
Logged

Lemunde

  • Bay Watcher
    • View Profile
Re: Pathfinding question
« Reply #6 on: July 06, 2010, 02:28:29 pm »

In situations like this there is always a default option, even if the programmer didn't mean to make one.  If the last path checked has the same length as the shortest path, it will either choose the last one or the shortest one, depending on the way the paths are compared.  It's always one or the other, never both.  Of course a clever programmer might choose to make it choose between the paths randomly but there really isn't much point.
Logged

Noble Digger

  • Bay Watcher
    • View Profile
Re: Pathfinding question
« Reply #7 on: July 06, 2010, 03:21:49 pm »

It took me about 2 minutes to make a room like that in my fort and try it out. I've seen lone dwarves choose either path, and if multiple dwarves are in this section at once, they will take opposite paths if necessary to avoid steping over each other. Sometimes, they will even go partly down one of the paths and then turn around and take the other path to avoid a dwarf in the original path.
Logged
quib·ble
1. To evade the truth or importance of an issue by raising trivial distinctions and objections.
2. To find fault or criticize for petty reasons; cavil.