Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 28 29 [30] 31 32 ... 43

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

numerobis

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #435 on: December 10, 2009, 03:06:28 pm »

The hierarchical approach also is inherently more parallelizable.  So a good sequential HAA* is indeed the goal.
Logged

qwertyuiopas

  • Bay Watcher
  • Photoshop is for elves who cannot use MSPaint.
    • View Profile
    • uristqwerty.ca, my current (barren) site.
Re: Anouncing The PathFinder Project
« Reply #436 on: December 10, 2009, 05:26:09 pm »

...

There are a couple important things you can do to optimize performance.
1: work less.
2: work smart.
3: do more work at a time.

...

There is a fourth option in situations such as this:
4: Use ALL of your time.

For example, when the game is paused, or most of the dwarves are asleep, or any other low-pathing-required situation, that is when you should have it seek for slight optimizations that take time for minimal gain, since you can afford to spend a whole second of game-paused time to optimize the placement of a zone, since the game is paused, thus you have free processing power, not being used anywhere.

With "new ore" announcements, that is common.

If you make the slow-optimization-search a pausable background thread, then it can be paused during any pathing and resumed when there is processing break. That way you don't waste idle time, even if the gains are minimal.
Logged
Eh?
Eh!

CobaltKobold

  • Bay Watcher
  • ☼HOOD☼ ☼ROBE☼ ☼DAGGER☼ [TAIL]
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #437 on: December 10, 2009, 05:42:26 pm »

With "new ore" announcements, that is common.
Mind that that's like to go away next version.
Logged
Neither whole, nor broken. Interpreting this post is left as an exercise for the reader.
OCEANCLIFF seeding, high z-var(40d)
Tilesets

Shades

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #438 on: December 11, 2009, 03:44:49 am »

There is a fourth option in situations such as this:
4: Use ALL of your time.

This is 'free' if we have multiple pathing threads, although only for paths already requested.

Most home multi-core systems are around 2 or 4 cores and though a jump to 8 cores is inevitable it's not going to happen for a while.  This means your maximum performance gain is around a factor of 4, realistically a factor of 3. 

Better algorithms utterly blows that out of the water, improvement can be factors of 10 for an optimized hierarchical pathfinder vs an optimized non-hierarchical approach, all the papers I've read confirm this.  Add a cache on top of that and we can probably get another factor of 10 improvement. 

Better algorithms are always good, but in this particular case multiple threads should be minimal effort as it's an isolated situation (calling pathing finding for a single path) that will trigger it. So although I agree that a better gain is possible and would encourage you to work on a better algorithm we might as well grab low hanging fruit where we can.

Also it won't be wasted work because even if you find an incredible algorithm it can still take advantage of the multiple threads.
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

Starver

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #439 on: December 11, 2009, 11:04:19 am »

stuff :)
I think you misunderstood my post, I wasn't talking about doing any extra/speculative pathfinding, only to 'background' the current pathfinding so it doesn't tie up main game thread. Like you say when a number of new dwarfs enter the map there is no reason for the game to freeze.
Sorry, there'd been talk about such stuff[1], and I misread your post as a continuation of same. :)

[1] Assuming I didn't misread that wrongly!
Logged

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #440 on: December 12, 2009, 03:12:10 am »

Ok got an automated test suite running, it tests combinations of randomly selected passable points.  A bunch of relavent info is written to file (I'll put it on the screen too soon).  If you have underground features like chasms or pits which have a lot of disconnected areas then path requests in these areas will result in the worst case 'flood the world' behavior but the system doesn't crash or anything totally horrible you'll just see low performance.  I know from manual tests that graph reads per path step of around 7 and nodes opened of near 1 is optimum, generally this means strait-line from start to goal, kinks and bends will slow things down considerably.  The test suites of course going to have a lot lower performance.

I'm going to work next on some connectivity management tracking so these situations are handled gracefully, this should bump up performance considerably,  I'll also explore bidirectional searches and other optimizations that can be done to plain non-hierarchical A*.
Logged
Khazad the Isometric Fortress Engine
Extract forts from DF, load and save them to file and view them in full 3D

Khazad Home Thread
Khazad v0.0.5 Download

piupau

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #441 on: December 12, 2009, 06:41:58 am »

Ok got an automated test suite running, it tests combinations of randomly selected passable points.  A bunch of relavent info is written to file (I'll put it on the screen too soon).

This is a very interesting project. I just read through the thread, and suggest that you'd put that test suite up for grabs in the first post -- It would give a much more 'upbeat' feeling to reading through all the posts knowing that there was something released in the end.  :)
Logged

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #442 on: December 12, 2009, 01:51:27 pm »

Use the Khazad SVN to grab the latest code, I recommend Tortoise SVN if you use windows.
Logged
Khazad the Isometric Fortress Engine
Extract forts from DF, load and save them to file and view them in full 3D

Khazad Home Thread
Khazad v0.0.5 Download

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #443 on: December 18, 2009, 12:02:26 am »

An effective system for establishing connectivity of different map areas is in place now and used in the testing suite.  I'm now experimenting with a new round of optimizing the Astar implementation itself.



Here is a screen shot of the new output info, this is a test of 100 random point pair path attempts.  As you can see 3 paths are rejected for non connected regions while the rest succeed.  Theirs a great deal of information on nodes and graph reads here but the Time efficiency is the simplest thing to understand, its milliseconds per tile in the path.  This can be made a lot better, when doing a relativly easy path on open ground I can get about 100th the time per step, this is because of pathing in internal areas ware dead ends mean that simple heuristics breakdown, a hierarchical solution should reduce this.
« Last Edit: December 18, 2009, 01:47:58 am by Impaler[WrG] »
Logged
Khazad the Isometric Fortress Engine
Extract forts from DF, load and save them to file and view them in full 3D

Khazad Home Thread
Khazad v0.0.5 Download

sir monko

  • Bay Watcher
    • View Profile
    • wsa
Re: Anouncing The PathFinder Project
« Reply #444 on: December 18, 2009, 05:10:00 pm »

very nice, impaler!

if someone's interested in what a* looks like in action, i put a demo together (and maybe caused a firefox 3.6 delay, due to the code revealing a performance bug):

here it is:
http://jsastar.tapirpirates.net/dfdemo/

this is just something i hacked together in my free time in the last 2 days, so it's definitely not optimized or anything. it works for drawing wiggling lines though.

i recommend google chrome for best performance. i tested it in recent versions of FF > 3.5, chrome, safari and opera. ie does - of course - not work (it needs the canvas element, and i shudder if i think about ie performance).

disclaimer: i'm not responsible if it locks up your browser!
Logged

Impaler[WrG]

  • Bay Watcher
  • Khazad Project Leader
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #445 on: December 19, 2009, 07:55:24 pm »

After a bit of optimizing performance has improved to 0.33 milliseconds per path step, a 250% improvement, more optimization is in the works, then I'll apply what I've learned to the Hierarchical implementation.

UPDATE:  0.23  ;D
« Last Edit: December 19, 2009, 08:37:41 pm by Impaler[WrG] »
Logged
Khazad the Isometric Fortress Engine
Extract forts from DF, load and save them to file and view them in full 3D

Khazad Home Thread
Khazad v0.0.5 Download

zchris13

  • Bay Watcher
  • YOU SPIN ME RIGHT ROUND~
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #446 on: December 19, 2009, 08:52:42 pm »

Logged
this sigtext was furiously out-of-date and has been jettisoned

Draco18s

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #447 on: December 19, 2009, 09:39:40 pm »

UPDATE:  0.23  ;D
What does this mean?

I think that his algorithm is so efficient that it takes an average 0.23 milliseconds per tile in a path, down from 0.33 (down from 1.16).
Logged

zchris13

  • Bay Watcher
  • YOU SPIN ME RIGHT ROUND~
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #448 on: December 19, 2009, 09:43:56 pm »

Can I assume that that is blazing "set the atmosphere on fire" fast?
Logged
this sigtext was furiously out-of-date and has been jettisoned

Fieari

  • Bay Watcher
    • View Profile
Re: Anouncing The PathFinder Project
« Reply #449 on: December 19, 2009, 09:46:45 pm »

Imagine having 5 times as many dwarves in your fort at the same speed you're running now. And this before the additional optimizations are going in.

Now we just need to add in connectivity maps for more movement types...
Logged
Pages: 1 ... 28 29 [30] 31 32 ... 43