Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 41 42 [43]

Author Topic: Anouncing The PathFinder Project  (Read 80304 times)

Draco18s

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #630 on: June 14, 2010, 04:32:44 pm »

Congrats, you've successfully been a waste of time :P

Mine, yours, and everyone else's.
Logged

HebaruSan

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #631 on: June 15, 2010, 09:01:01 am »

Quote
The trick is just getting the cost correct.
Agreed.  Utterly.

(I don't have the full conversational context here, but I assume you mean the pathing cost to build a bridge as compared to walking across empty tiles?)

I think that cost should vary according to the preferences of each goblin commander. This would reduce the monotony and solvability of gameplay--rather than the path engine generating a single (sub-)optimal path for all goblins to follow through each possible maze, you could have different squads exploring different branches, so more of your design would be used. Maybe Goblin Commander A prefers to stick to solid ground whenever possible, while Goblin Commander B knows that at least his own bridge tiles won't have traps. The distribution could be a nice bell curve centered around the real excess time it takes to build bridges.

Also, should fog of war factor in at all here? Everyone still seems to be assuming that newly arrived goblins would plan their route through your defenses based on a complete knowledge of the floor plan. I wouldn't mind seeing some of them track down a completely suboptimal route on their first try, only to be ambushed by crack marksdwarves (and presumably somehow warn the others, so their strategy can adapt over time).
Logged

madk

  • Bay Watcher
    • View Profile
    • pineapplemachine
Re: Anouncing The PathFinder Project
« Reply #632 on: June 15, 2010, 12:29:14 pm »

I'm no expert on pathfinding, so I can't vouch for the integrity of these methods, but it's the system I conceived for use in my own game I've been considering making.


So you've got a dwarf or animal that suddenly decides it needs to get from point A to point B.

Step 1 is to use A* to find a path from A to B, if one exists. If a path does not exist, the dwarf cancels whatver action it needed the path for. The intelligence of the creature would have a weight on how strong the influence of the Steven van Dijk heuristic is upon the calculation. (The Steven van Dijk heuristic causes the path to follow a straight line upon the grid rather than an equally long movement along a more staggered path)

Step 2 involves finding which nodes along the generated path have an uninterrupted path between them and records only these "important" nodes. Fig. 1 illustrates the full A* path, fig. 2 demonstrates the result.

Figure 1:
Code: [Select]
#############
#     xxx   #
#    x###x  #
#   x # # x ##########
#  x  # #  xxxxxxxxB #
#  A  # ##############
#######

Figure 2:
Code: [Select]
#############
#     X X   #
#     ###   #
#     # #   ##########
#     # #  X       B #
#  A  # ##############
#######

Step 3 sees the dwarf travelling a simple straight line from one node to the next.



Although this adds a bit of time for te initial computation, its effect becomes prominent when the path becomes somehow altered.
So let's suppose that the path has been interrupted - say a door locked or a bridge retracted, but for the sake of example, another, different path has been opened up. In any case, we end up with fig. 3.

Figure 3:
Code: [Select]
#############
#     X#X   #
#     ###   #
#     # #   ##########
#     # #  X       B #
#  A  # ## ###########
####  #  # #
   #  #### #
   #       #
   #########

For a small example such as this, the effect is less darastic, but here's what happens.
The original path is remembered, but a new path is construced. However, this path is no longer from A to B, but rather from the node the dwarf's current position to the next node on the path. The newly constructed A* path should look like this:

Figure 4:
Code: [Select]
#############
#     ☻#X   #
#    x###   #
#   x # #   ##########
#   x # #  X       B #
#  Ax # ##x###########
####x #  #x#
   # x####x#
   #  xxxx #
   #########

If the following node can't be reached, it does a check on B to ensure the target is still reachable, then goes down the line until it finds the next reachable node. The disadvantage is that the path ends up being longer - but the movement does become more natural and less artificial.

And, of course, the reduction is performed on this new path, as well, as portrayed in fig. 5.

Figure 5:

Code: [Select]
#############
#     ☻#    #
#     ###   #
#   X # #   ##########
#     # #  X       B #
#  A  # ## ###########
####X #  # #
   #  #### #
   #  X  X #
   #########

numerobis

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #633 on: June 19, 2010, 12:40:37 am »

Currently the cost appears to be in the original search, not in following the planned path.  A dwarf that has a path walks up to an obstruction added subsequent to the search and acts all confused -- which is actually pretty amusing to watch.  This is not to say that your idea is bad, just that I don't think it improves performance in the case of DF.  The memory consumption reduction is nice, but it isn't all that important when we're talking a mere ~200 dwarves walking a distance of ~200.

Your system will have arbitrarily suboptimal behaviour when the repath allows a shorter path that doesn't go through the precomputed waypoints.  In figure 4, for example, I'm not sure why the path isn't hitting the second waypoint at the top.  According to the algorithm you have described, it should try and succeed to path to it.
Logged

LShadow

  • Bay Watcher
  • The moon's on fire!
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #634 on: March 06, 2011, 05:08:36 pm »

Whatever happened to this project? Is it still ongoing?
Logged
What is hydrogen? It's a substance which, if you leave enough of it sitting around long enough, completely unsupervised, becomes life that eventually evolves into something complicated enough to ask the question 'What is hydrogen?'

j0nas

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #635 on: March 06, 2011, 05:56:20 pm »

Posting in epic (dead)thread to be able to find my way back to it later.
Logged

Urist McBusDriver

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #636 on: March 07, 2011, 07:06:08 am »

Posting in epic (dead)thread to be able to find my way back to it later.
You could just click on the 'Notify' button at the bottom of the thread to subscribe to it...
Logged
Of course, since he doesn't actually walk around counting things, we can only assume that bookkeeping time is spent in deep meditation, psychically sensing exactly how many piles of orthoclase there are. It takes a while to hone a skill like that.

Shades

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #637 on: March 07, 2011, 07:35:02 am »

You could just click on the 'Notify' button at the bottom of the thread to subscribe to it...

The interface for threads you've posted in is much nicer than the notify button version. Shame really because if they combined it it would be nice to un-notify from threads you posted in as well.
Logged
Its like playing god with sentient legos. - They Got Leader
[Dwarf Fortress] plays like a dizzyingly complex hybrid of Dungeon Keeper and The Sims, if all your little people were manic-depressive alcoholics. - tv tropes
You don't use science to show that you're right, you use science to become right. - xkcd

Assassinfox

  • Bay Watcher
  • [FANCIFUL]
    • View Profile
    • Raging at the Box
Re: Anouncing The PathFinder Project
« Reply #638 on: March 08, 2011, 07:17:58 pm »

Narmio

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #639 on: March 08, 2011, 08:08:23 pm »

Yeah, this thread ended... Badly. Invader got a little full of himself and did some stuff that he really should have known better than to try.

Which is a shame, as there's rather a lot of information in this thread that may be of use to Toady when the time comes to revisit pathfinding. One thing we could do is have some computer sciencey type go through this thread and pull out all the interesting and potentially useful suggestions, then present a summary in a new thread and restart the discussion from there. Excise the knowledge from its checkered past, as it were.
Logged
Pages: 1 ... 41 42 [43]