Pathfinding Crash

[mefistotelis]

Originally reported on Google Code with ID 391

Unique to my map though, at least it's the only one i've seen it happen on.
Download the attachment and sit around for 15~ seconds. KeeperFX will crash.

Log file contains a whole lot of;
Error: tri_new: ix_Triangles overflow

followed by;
Error: triangle_find8: No position pointed at 57984,58752 (that number specifically
pops up a lot)


Dungeon Keeper FX ver 0.4.5.1411

Reported by Woudo@hotmail.com.au on 2014-10-11 08:05:36

---

- _Attachment: [map300.rar](https://storage.googleapis.com/google-code-attachments/keeperfx/issue-391/comment-0/map300.rar)_

[mefistotelis]

This is a known phenomena with very complex maps. You need to simplify the map so KeeperFX
can cope with the pathfinding. Also best to put some extra impenetrable rock around
the edges. Funny visuals can occur if maps go right to the edges.

good luck! Dayo

Reported by dayokay65 on 2014-10-11 13:04:34

[mefistotelis]

These words hurt me.

Reported by Woudo@hotmail.com.au on 2014-10-12 17:43:34

[mefistotelis]

Well, for now it cannot be solved any other way.

KeeperFX would have to be almost completely rewritten before pathfinding-related arrays
can be enlarged.

Reported by mefistotelis on 2014-10-14 21:29:22

• Status changed: Accepted

[mefistotelis]

There is no way I can diminish this level. There is something inherently broken about
it.

In the below attachment I have;
Removed every single imp and fly from the map. There is ZERO creatures on the map now.
Reduced every Keeper to a single portal each.
Stripped out all of the script aside from Initial and Keeper setups.
Fixed a scripting error in Initial setup (SET_GENERATE_SPEED(PLAYER0,400). Whoops.

It still crashes after ~15 seconds. I've figured out the crash is caused by the enemy
keepers generating their first creature from a portal. Every single time it has crashed,
the purple keeper has just received a fly.

It isn't pathfinding. The regular log says nothing and frankly, I can't decipher what
information is actually relevant in the heavy log.

Reported by Woudo@hotmail.com.au on 2014-10-15 10:40:11

---

- _Attachment: [map300 pocket edition.rar](https://storage.googleapis.com/google-code-attachments/keeperfx/issue-391/comment-4/map300 pocket edition.rar)_

[mefistotelis]

We weren't clear in what to simplify - sorry for that.

Pathfinding arrays can be exceeded when TERRAIN is too complex - has many tunnels,
often changes between lava/path/water, makes travelling path complicated.

The amount of creatures and objects has nothing to do with pathfinding - objects are
not part of terrain analysis.  Same goes to script commands. These items have their
own limits, but these limits have no influence on pathfinding.

Reported by mefistotelis on 2014-10-15 21:56:03

[mefistotelis]

I've taken a look at the map, and it is no wonder the pathfinding crashes on this, it
is completely filled with tunnels and countless ways of getting from point a to point
b.

I know the map will play out completely different, but what will stop the map from
crashing is if you would fill out all the dug out paths with dirt. An not dig everything
out during playing of course.

Reported by Loobinex on 2014-10-15 22:07:02

[mefistotelis]

THESE WORDS ARE MORE PAINFUL THAN THE LAST.

Reported by Woudo@hotmail.com.au on 2014-10-16 03:43:33

[mefistotelis]

Is the number of creatures irrelevant then? I always assumed that in a complex map,
a higher number of creatures made it worse, as they all needed to continuously compute
paths to navigate through the map?

Reported by dayokay65 on 2014-10-17 09:21:47

[mefistotelis]

I think this is fixable. I removed the army of flies, and filled in some of the map
with earth, as Loobinex suggested. Game ran for 10 minutes without any problems. You
could add the flies back via an action point when their area is discovered (this would
stop the hero flies attacking the blue or green keepers too). I have attached the version
I made if it's any use (I also enabled keeperFX commands so I could make the map visible
straight away - see the script file)

oh - and the set generate speed was invalid - now fixed.

cheers,

dayokay

Reported by dayokay65 on 2014-10-18 15:46:35

---

- _Attachment: [map300dk-edit.7z](https://storage.googleapis.com/google-code-attachments/keeperfx/issue-391/comment-10/map300dk-edit.7z)_

[Loobinex]

@mefistotelis Is it possible the last few months there's an extra bug in the code that causes more pathfinding problems? Many maps seem to suffer. Attached a log and packet file from Burdened Imp map 222 that freezes the game.

(Save as .zip file)

[mefistotelis]

It is more likely that it's not a new bug, but old one which become more apparent.

Pathfinding consists of two major routines:

• updating regions map when map layout changes (ie. digging makes new regions and connections, lava trap makes places not passable, etc)
• triangulating a path for specific creature to go to specific place (ie. imp wants to go to treasury, then he asks Ariadne for a path)

Now, every function which is either related to creature state or map state, affects the pathfinding component. Every time we rewrite such a function - more of rewritten pathfinding is used. This means if there's a bug in rewritten code - it is being used more often as development progresses.

I believe there is some kind of error in rewritten pathfinding, and I spent quite lot of time trying to debug it - but unfortunately I don't have enough time to make one long debug session, and debugging such complex issue with interrupts is almost impossible.

[Loobinex]

Is there something I can provide (apart from more time) that can help you out?

[mefistotelis]

The only way to solve that is to debug the cause.

If we won't be able to do it with what we have, due to complexity of the issue, then we'll have to prepare tools which would decrease the complexity.

For example:

• show creature paths as lines on screen
• show pathfinding regions and connections on screen
• detach the pathfinding to be a proper detachable unit, and test it with unit tests

Now to answer your question, Loobinex - I don't think you can help in any other way than updating issues each time you see the problem. What would help is a test map where the problem happens always, and happens relatively fast after starting the map, but I realise it's not easy to get this.

When I tried to debug pathfinding, I used a map you listed as faulty in one of your issues. On this map, (can't remember which, sorry) at some point, a computer player imp was getting stuck on dungeon heart pedestal. But this was happening after about 1 hour of gameplay, and that was taking quite some time even in frameskip mode. To debug this back to the cause, I had to make a packet file and run it over and over, many times. This also meant that any other update to the code was leading to desychronization of packet file and starting the process from the beginning.

[Loobinex]

Providing such a map is the easiest thing in the world. I assumed with this being such a well known problem you would have had your own test-map for this already.
Attached is a map where the hang occurs in about 3 seconds, it is a really common hang and you have to design your maps in such a way to avoid this problem. When I make a map I first make a prototype to see if it works or hangs and even then when you actually play the final version you might have to throw it away. Others on the forum have also been complaining how difficult it is to make a map with a little dept that doesn't hang straight away.

To reproduce load the attached map (called pathfinding crash), build some imps, mark a path towards the portal and drop and imp to dig and the game will freeze.

(Save as, rename to .zip)

[mefistotelis]

Ok then; I'm now focused on refactoring the keeperfx-stable repository, but when I'm done I will take a look at this (unless someone will do it earlier).

[Loobinex]

To help, two versions of the same map from Woudo. One freezes straight away the other one lasts longer but differs only a few tiles.

(Right click, save as, .rar instead of .jpg)

[Loobinex]

Here's another one that hangs straight away:

[Loobinex]

This is a new record for me. This map from the database hangs the game before you're even out of the floating spirit: 00425_hero_invasion04.zip

This is an interesting comparison, as when I tried it in an old version (0.4.4.976) i could play a good 5 seconds before the game hung.

EDIT: I updated the map in the database, it hung because the map was corrupted. Version 6 is fine, version 5 hung.

[Loobinex]

Apparently also happens in the main campaign as well. See this topic.

[Loobinex]

@Trotim found out that what really helps in preventing the pathfinding bug is to make sure maps have 'filled corners'. So for ADiKtEd open the map.ini and set these settings 'FRAIL_COLUMNS=0, UNAFFECTED_GEMS=1, UNAFFECTED_ROCK=1' and make/update the map with these settings in place.

This strongly reduced the amount of triangles, and the pathfinding bug occurs when there are over 9000 triangles.

[Loobinex]

Fixed in Loobinex/keeperfx-unofficial@7d60638