Print

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

[decimamas]

As a (modest) software developer, i know how much is difficult to have a good performance pathfinding algorithm.

I may suggest to implement a workaround (switchable, maybe), consisting of marking some points in the map as "checkpoints" (let's name them as C1, C2, etc), then you can calculate an efficient static route between them.

So, if I have to go from point A to point B, currently your pathfinding algorithm try his best then give up if the path is too difficult.
With my suggestion, you may avoid this by calculating a path from A to C1, then appending C1 to C2 static route, and then calculating C2 to B.

For sure, it's not optimal nor realistic (eg. maybe B could be reached with less steps) but it may help CPU overheading, which is currently an issue.

I had a map like this:
                     ________
_____________|           |
|           |                    |
|     |     |             A     |
|   _|_________            |
|  |                |_______|
|  |
|  |
|  |______________________________       ____      _____     ____
|                                                  |      |      |     |      |   |      |
|____________________________     |      |   |  |     |  |   |  |   |  |
                                              |    |      |   |  |     |  |   |  |   |  |
                                              |    |____|  |   |___|  |   |_|   |  |___
                                              |_________ |________|_____ _|_____  B


and dwarves didn't managed to get from A to B, they gave up their pathfinding try. In this case, i think a checkpoint placement could solve the issue:

                     ________
_____________|           |
|           |                    |
|     |     |  (C1)     A     |
|   _|_________            |
|  |                |_______|
|  |
|  |
|  |______________________________       ____      _____     ____
|                                                  |      |      |     |      |   |      |
|____________________________     |      |   |  |     |  |   |  |   |  |
                                              |    |      |   |  |     |  |   |  |   |  |
                                              |    |____|  |   |___|  |   |_| Z |  |___
                                              |_________ |________|_____ _|___(C2) B

as you have to calculate on-the-fly just small steps.
Obviously, the same A-C1-C2 steps would apply to go to point Z, causing dwarf to go back and forth for some steps, but that would not be that bad.

Just my two cents.

Kudos to you Toady and all the community!

[Osmosis Jones]

Try here.

http://www.bay12games.com/forum/index.php?topic=43265.0

[Sowelu]

With much respect for your programming skill, there's been five billion threads on this, and every single one of them has had people with MASSIVE programmer cred weighing in.

It's the most over-debated technical issue here, and I just want to warn you--trying to add your ideas on this very specific topic is probably just going to leave you disappointed.