Print

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

[numerobis]

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

[qwertyuiopas]

...

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.

[CobaltKobold]

With "new ore" announcements, that is common.

Mind that that's like to go away next version.

[Shades]

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.

[Starver]

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!

[Impaler[WrG]]

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*.

[piupau]

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. 

[Impaler[WrG]]

Use the Khazad SVN to grab the latest code, I recommend Tortoise SVN if you use windows.

[Impaler[WrG]]

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.

[sir monko]

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!

[Impaler[WrG]]

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 

[zchris13]

UPDATE:  0.23 

What does this mean?

[Draco18s]

UPDATE:  0.23 

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).

[zchris13]

Can I assume that that is blazing "set the atmosphere on fire" fast?

[Fieari]

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...