Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[zwei]

What about making use of player-pauses?

Active player pauses game quite often and it is ideal time to run more expensive pathing optimizations or to run pather preventively (example for miner was given. It is not so far fetched for pather to precalculate his path for dozens on mined squares.)

Also, lag spikes usually happen right after player unpauses after giving commands that result in huge amount of pathing (i.e. moving goods to trade depot, mass dumping something). For example as player marks goods to be transfered, pather can begin to calculate path for hauler to item and further patch with item to trade depot. When player leaves dialog and unapauses, precalculated paths are committed.

Especially useful for wagons as game pauses when caravan arrives and wagon pathing is expensive.

[NoahTheDuke]

What about making use of player-pauses?

That's been discussed and rejected at least five times so far.

Noah

[Akhier the Dragon hearted]

In a lot of the post I see people talking about breaking areas down into small subsections and what not. if from there you made just ........ tip of the tongue and it just wont come off here have an example of what I am trying to say, sorry if this is what someone has already suggested and I just did not understand it because of it going over my head or me just missing it becuase I just read this whole thread in a couple hours straight.

Spoiler (click to show/hide)

a dwarf wants to get from point a in block A through block B to point c in block C
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
would it be easier to before you even had to path that just go through and say the optimal path P from A to C it like so:
  A     B     C
##### ##### #####
#+### #+++# #++##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
then when you need to make the path all that would need to be done it path from point a to the edge of block B and from point c to the edge of block B
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
and a quick check to make sure that path P was still clear
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
making a complete path that only had to check a few things. this should get more and more efficient the farther the distance between point a and point c like so:
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
where once again you would only need to calc point a to edge of block B and from point c to edge of block E
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
then do a quick check that the optimal paths in between where still clean
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
to make a quick path because you did not have to actually check all of B, D, and E
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
of course the farther you have to go the more likely an interruption is so maybe in block B you had to go around that loop because of a wall
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +##++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
or somewhere in D it was completely blocked so you had to take a route farther out of the way but you would still have optiomal paths once you get to going between blocks:
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ ++#++ +++++ +++##
##### ##+## ##### ##### #+###
  F     G     H     I     J
##### ##+## ##### ##### #+###
##### ##+## ##### ##### #+###
##### ##+++ ++#++ +++++ +++##
##### ##### #+++# ##### #####
##### ##### ##### ##### #####
as pointed out in other posts in this thread the area is already quasi split between embark tiles and you could probably use any of the other nifty ways to break up the area as needed.

this is the best I can explain what I am thinking. Most of my programming experience is with vb.net and c# so all the talk about A* is over my head by a bit. Also as a question I am currently learning programming in collage and in my free time, what language should I learn if I want to make games more specifically roguelike games?

[Andir]

In a lot of the post I see people talking about breaking areas down into small subsections and what not. if from there you made just ........ tip of the tongue and it just wont come off here have an example of what I am trying to say, sorry if this is what someone has already suggested and I just did not understand it because of it going over my head or me just missing it becuase I just read this whole thread in a couple hours straight.

Spoiler (click to show/hide)

a dwarf wants to get from point a in block A through block B to point c in block C
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
would it be easier to before you even had to path that just go through and say the optimal path P from A to C it like so:
  A     B     C
##### ##### #####
#+### #+++# #++##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
then when you need to make the path all that would need to be done it path from point a to the edge of block B and from point c to the edge of block B
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
and a quick check to make sure that path P was still clear
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
making a complete path that only had to check a few things. this should get more and more efficient the farther the distance between point a and point c like so:
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
where once again you would only need to calc point a to edge of block B and from point c to edge of block E
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
then do a quick check that the optimal paths in between where still clean
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
to make a quick path because you did not have to actually check all of B, D, and E
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
of course the farther you have to go the more likely an interruption is so maybe in block B you had to go around that loop because of a wall
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +##++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
or somewhere in D it was completely blocked so you had to take a route farther out of the way but you would still have optiomal paths once you get to going between blocks:
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ ++#++ +++++ +++##
##### ##+## ##### ##### #+###
  F     G     H     I     J
##### ##+## ##### ##### #+###
##### ##+## ##### ##### #+###
##### ##+++ ++#++ +++++ +++##
##### ##### #+++# ##### #####
##### ##### ##### ##### #####
as pointed out in other posts in this thread the area is already quasi split between embark tiles and you could probably use any of the other nifty ways to break up the area as needed.

this is the best I can explain what I am thinking. Most of my programming experience is with vb.net and c# so all the talk about A* is over my head by a bit. Also as a question I am currently learning programming in collage and in my free time, what language should I learn if I want to make games more specifically roguelike games?

I have also thought about this, but apply your same logic to a flat open plane.  Where you enter each block would determine the shortest path.

[shadow_slicer]

In a lot of the post I see people talking about breaking areas down into small subsections and what not. if from there you made just ........ tip of the tongue and it just wont come off here have an example of what I am trying to say, sorry if this is what someone has already suggested and I just did not understand it because of it going over my head or me just missing it becuase I just read this whole thread in a couple hours straight.

Spoiler (click to show/hide)

a dwarf wants to get from point a in block A through block B to point c in block C
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
would it be easier to before you even had to path that just go through and say the optimal path P from A to C it like so:
  A     B     C
##### ##### #####
#+### #+++# #++##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
then when you need to make the path all that would need to be done it path from point a to the edge of block B and from point c to the edge of block B
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
and a quick check to make sure that path P was still clear
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
making a complete path that only had to check a few things. this should get more and more efficient the farther the distance between point a and point c like so:
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
where once again you would only need to calc point a to edge of block B and from point c to edge of block E
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
then do a quick check that the optimal paths in between where still clean
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
to make a quick path because you did not have to actually check all of B, D, and E
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
of course the farther you have to go the more likely an interruption is so maybe in block B you had to go around that loop because of a wall
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +##++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
or somewhere in D it was completely blocked so you had to take a route farther out of the way but you would still have optiomal paths once you get to going between blocks:
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ ++#++ +++++ +++##
##### ##+## ##### ##### #+###
  F     G     H     I     J
##### ##+## ##### ##### #+###
##### ##+## ##### ##### #+###
##### ##+++ ++#++ +++++ +++##
##### ##### #+++# ##### #####
##### ##### ##### ##### #####
as pointed out in other posts in this thread the area is already quasi split between embark tiles and you could probably use any of the other nifty ways to break up the area as needed.

this is the best I can explain what I am thinking. Most of my programming experience is with vb.net and c# so all the talk about A* is over my head by a bit. Also as a question I am currently learning programming in collage and in my free time, what language should I learn if I want to make games more specifically roguelike games?

The pathfinding code we're currently playing around with already implements such caching. In some cases it does significantly increase pathing speed. The bigger benefit from hierarchical pathing will be in the way it limits the size of the search space (i.e. if you know that B and C are not connected but D is connected to B and C, then you won't try to find a path to c from within B. Instead you should path towards D first). I don't think that part is fully implemented  .

[Draco18s]

Spoiler (click to show/hide)

a dwarf wants to get from point a in block A through block B to point c in block C
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
would it be easier to before you even had to path that just go through and say the optimal path P from A to C it like so:
  A     B     C
##### ##### #####
#+### #+++# #++##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
then when you need to make the path all that would need to be done it path from point a to the edge of block B and from point c to the edge of block B
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
and a quick check to make sure that path P was still clear
  A     B     C
##### ##### #####
#a### #+++# #c+##
#+### #+#+# ##+##
#++++ +++++ +++##
##### ##+## #+###
making a complete path that only had to check a few things. this should get more and more efficient the farther the distance between point a and point c like so:
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
where once again you would only need to calc point a to edge of block B and from point c to edge of block E
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
then do a quick check that the optimal paths in between where still clean
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
to make a quick path because you did not have to actually check all of B, D, and E
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
of course the farther you have to go the more likely an interruption is so maybe in block B you had to go around that loop because of a wall
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +##++ +++++ +++++ +++##
##### ##+## ##### ##### #+###
or somewhere in D it was completely blocked so you had to take a route farther out of the way but you would still have optiomal paths once you get to going between blocks:
  A     B     D     E     C
##### ##### ##### ##### #####
#a### #+++# ##### ##### #c+##
#+### #+#+# ##### ##### ##+##
#++++ +++++ ++#++ +++++ +++##
##### ##+## ##### ##### #+###
  F     G     H     I     J
##### ##+## ##### ##### #+###
##### ##+## ##### ##### #+###
##### ##+++ ++#++ +++++ +++##
##### ##### #+++# ##### #####
##### ##### ##### ##### #####
as pointed out in other posts in this thread the area is already quasi split between embark tiles and you could probably use any of the other nifty ways to break up the area as needed.

Of course, the paths you're suggesting be cached there are extremely trivial to recalculate (probably more so than to look them up).  They're strait-line in a 1 tile wide corridor.

[SkyRender]

 I'm not sure how practical it is (or if anything like it has been suggested), but it seems to me that the main issue here is the search algorithm for "nearest item" more than the actual pathfinding to the object.  It would make sense to improve that first, instead of using the existing "find nearest in terms of sheer physical distance" algorithm.  What I came up with for that is a sort of radial trailer pathfinding algorithm.  It's directly fractal at the moment and could use some refinement as a result, but I think it's on the right track.

 Basically, it works something like this: for east, north, west, south, up, and down, perform an expanding cone of searches out 1 tile "forward", "up-forward", "down-forward", above, and below (for cardinal directions; up/down it'd get a lot messier since you'd have to do a genuine 9-tile radial search).  If an acceptable item is found (or the trailer in that direction is impassible), its location and distance are noted (if there was an item; otherwise, it returns null) and that trailer of the search is cut off.  Repeat until all trailers either locate something or null out, then do a comparison to find the genuinely closest object.  This would lead to a LOT of trailers, and some noticeable search overlap, but it would also have very thorough coverage.  Its main issue (besides the massive number of small checks) would be very odd layouts with lots of corners.

[Exponent]

...

Sounds like a straight-forward breadth-first search, which unfortunately tends to be very slow and consumes a lot more memory.

The theme for this thread has largely been about how to improve pathfinding performance, with pathfinding quality being secondary, so improving the nearest item search has taken a bit of a back seat.  And rightly so, in my opinion.  It's a tough nut to crack, but might be easier if general pathfinding is significantly improved.  Especially if a lot of useful data gets cached in such a way that it can be used to also make some quick guesses about which items are truly closest.  The hierarchical stuff could help with that, for example, by providing very quick upper/lower bounds or estimates of costs from one area (dwarf) to another (potential item to grab).  That way, multiple potential items could be scanned quickly, and the ones that obviously involve a long path (despite being physically close) can be skipped over without a large hit to performance.

[Shades]

Sounds like a straight-forward breadth-first search, which unfortunately tends to be very slow and consumes a lot more memory.

Iterative depth first is probably a better option to solve this as although it takes longer the memory overhead is minimal.

[Akhier the Dragon hearted]

Of course, the paths you're suggesting be cached there are extremely trivial to recalculate (probably more so than to look them up).  They're strait-line in a 1 tile wide corridor.

If games really did always do straight line paths then okay, I just used them to make it easier on me, for instance I could have made the blocks be 100x100 and filled with the most odd and winding corridors you ever did see. also I look back on my idea and have realized that it should have been check that those paths where clear first because if it was not then you would not have already pathed anywhere you did not need to like in my example where you would have already pathed from point a to side of block B and so on when you might end up not even going into block B at all depending.

...

Sounds like a straight-forward breadth-first search, which unfortunately tends to be very slow and consumes a lot more memory.

The theme for this thread has largely been about how to improve pathfinding performance, with pathfinding quality being secondary, so improving the nearest item search has taken a bit of a back seat.  And rightly so, in my opinion.  It's a tough nut to crack, but might be easier if general pathfinding is significantly improved.  Especially if a lot of useful data gets cached in such a way that it can be used to also make some quick guesses about which items are truly closest.  The hierarchical stuff could help with that, for example, by providing very quick upper/lower bounds or estimates of costs from one area (dwarf) to another (potential item to grab).  That way, multiple potential items could be scanned quickly, and the ones that obviously involve a long path (despite being physically close) can be skipped over without a large hit to performance.

I figured that any of the precalc could be done during load up like everything else and that the goal was to make the pathfinding faster so I would be fine add a little extra time at start up for faster speed while playing.

[peterix]

I'm not sure how practical it is (or if anything like it has been suggested), but it seems to me that the main issue here is the search algorithm for "nearest item" more than the actual pathfinding to the object.  It would make sense to improve that first, instead of using the existing "find nearest in terms of sheer physical distance" algorithm.  What I came up with for that is a sort of radial trailer pathfinding algorithm.  It's directly fractal at the moment and could use some refinement as a result, but I think it's on the right track.

 Basically, it works something like this: for east, north, west, south, up, and down, perform an expanding cone of searches out 1 tile "forward", "up-forward", "down-forward", above, and below (for cardinal directions; up/down it'd get a lot messier since you'd have to do a genuine 9-tile radial search).  If an acceptable item is found (or the trailer in that direction is impassible), its location and distance are noted (if there was an item; otherwise, it returns null) and that trailer of the search is cut off.  Repeat until all trailers either locate something or null out, then do a comparison to find the genuinely closest object.  This would lead to a LOT of trailers, and some noticeable search overlap, but it would also have very thorough coverage.  Its main issue (besides the massive number of small checks) would be very odd layouts with lots of corners.

This assumes that looking up what item is at which coordinates is a free operation. It's a very expensive one. O(n), where n is the length of the item vector. It could make sense if it was O(log n) or O(1). Not like this.

I believe (based on my knowledge of the reverse-engineered internals), that locating the item is done by scanning the vector once and using some distance equation like this one: http://en.wikipedia.org/wiki/Taxicab_geometry

So, searching for the item works like this:

Code: [Select]

for each item
    test if the item is reachable
    if(reachable)
        if(distance to item < distance to final item)
            final item = itemI also believe that the 'reachable' test can be done 'for free', because DF stores information about the connected areas as part of its map (if item and dwarf are in disconnected areas, item is not reachable). This explains the lag from manipulating doors, floodgates and bridges using levers - the connected areas are recalculated.

[Draco18s]

The only problem with Taxicab Geometry with regards to stone distance is that the Z-axis is not as accessibly traversable as the X and Y are.

[Teiwaz]

Most of my programming experience is with vb.net and c# so all the talk about A* is over my head by a bit. Also as a question I am currently learning programming in collage and in my free time, what language should I learn if I want to make games more specifically roguelike games?

Language doesn't really matter all that much - A* is just an algorithm, and can be done in any language. (It, and variants, tend to be the most commonly used pathfinding algorithms as it's pretty much the best thing we have). I'd look into XNA (www.xna.com) - it's what "Xbox Live Arcade" games are built with, and it uses C#, so your experience with that language isn't wasted. (It can also be used to make windows games, windows phone games, etc.)

It's an excellent platform to develop on as a hobbyist, as it does a lot of the painful, low-level stuff for you so you can get on to the more interesting parts of the game. (Things like input, and it has an excellent content pipeline to get sprites, or even 3d models into the game easily, etc.)

[Akhier the Dragon hearted]

thanks Teiwaz!
next question should I learn some C and C++? it seems that many of the examples and stuff that I can find for roguelikes is in them and as I have learned from this thread DF is in C++.

On topic now I think that the movement forms could be done in a different way from what everyone seems to want with a different thing for walking flying and all that. you could build more of a tree with different forms of walking because flying is just walking with more area and walking is just where pets can walk plus doors that are tightly shut and so on. the only stand alone form of moving is swimming and even that ties in with amphibious creatures so you would not really have to build a giant list of where each movement form can go because that would have to much duplication of data and be inefficient.

also amphibious and magma swimmers are basically the same thing except for where they swim so the movement is the same, just in different liquids.

[Teiwaz]

thanks Teiwaz!
next question should I learn some C and C++? it seems that many of the examples and stuff that I can find for roguelikes is in them and as I have learned from this thread DF is in C++.

Don't bother with C, C++ will teach you everything C can do, and more. C can be a good stepping stone for C++, but C# will do just as well for that and will get you into an object-oriented way of thinking.

C++ is really, really powerful, but can be simply brutal. Absolutely learn it if your plans are to go into the industry as a programmer, but put it aside for now - C# will teach you most of what you need to learn about programming, and should last you a good long while. Go to C++ when you want to learn C++ - it can be a nightmare, especially if you're trying to get a working project out of it. Just getting something to compile can be a colossal pain in the butt, doubly so if you're trying to integrate other peoples' code to do the stuff you don't want to worry about (and I'm talking really low level stuff here, like polling the state of the keyboard or figuring out where the mouse is, or playing a sound that isn't a default windows beep, or loading an image into memory and displaying it on the screen).

There's a whole lot more to being a good programmer than knowing language X or Y. It's more about being able to figure out how to do things, being able to write easy-to-read, well commented, functional, efficient code, being able to squash bugs quickly and without causing new ones, and being able to familiarize yourself with a new codebase quickly, whatever the language. If you can do that, knowing the syntax and foibles of a particular language is secondary.