Pathnode Visualization

I am not entirely certain for what the pathnodes are used in ToEE (only NPC waypoints, or pathfinding in general?), but I added pathnode conversion and visualization to my engine and here is an example screenshot (vanilla ToEE, no mods):




Why exactly are the pathnodes connected like that? I mean the connections even go through walls. Shouldn't pathnodes only be connected to neighbours reachable by line of sight?

Please enlighten me

 

Well I want to do pathfinding differently anyway (no "tiles", but rather navigation meshes). I just have to know what the ToEE engine uses this information for. If it's just for NPC navigation (i.e. the sector file says that a NPC walks between waypoints A and B, that is easy enough), then I do need to import and use them. If they're *only* used to speed up pathfinding, I probably don't need to import them, because pathfinding will be fast enough without them.

 

But why pre-generate at all then?

 

Maybe the connections are mapped as "go / no go" ahead of time. And if "go", then the path is figured.

Or an overall path path is figured through several nodes, then the paths between each node are determined.

Or an old path-finding system was overlayed with a new one.

 

My uneducated opinion would be to agree with GA on #3. It was probably an abandoned system. My only reasoning for this is that we dont need to make path nodes for new maps (like WWB, HB, Hommlet Castle). It seems that the game can determine paths on its own now by knowing the location of impassable objects.

Then again, some parts of Hommlet follow horrible paths. Like going from the grandmother to the carpenters (east of Jaroo) it forces you to go north instead of south (which would save you time).

 

Gaear,

I know that the inside of the Hommlet castle does not have pathnodes and everything was fine. It was a pretty big map too... Hmm, who knows.

 

Actually there is. You could create a navmesh (that's what I am trying to do) based on the tile-information in the sectors, and use the centers of each polygon (bigger than a certain size) as a path node.

Anyway. I am currently working on pathfinding, and doing it *right* is harder than I thought. But certainly doable. I initially wanted to use something like Recast/Detour (http://code.google.com/p/recastnavigation/), which is a library for generating navmeshes automatically, but it doesn't translate well to the fine-grained 2d information I have. So, my current status is an abhorrently slow A* based on the original tiles (not going to use that), and an unfinished navmesh generator, which I am probably going to extend.

Here is a screenshot of the walkable rectangles (each drawn with a unique color to make them distinguishable) it generates for the interior of the moathouse:



I am not done with implementing all merging operations yet. Especially if merging two rectangles will create three rectangles.
I'll keep you posted.

 

Well, not really. Here's an image to illustrate:


Maybe I should've added that this is about axis aligned rectangles and that the merging has the goal of maximizing the area of (at least) one rectangle.

Not really. Pathfinding is a solved problem. The "hard" thing I was talking about was creating a navigation mesh from tile-based information. A very good article on pathfinding in general is this (not too technical, really!):
http://www.ai-blog.net/archives/000152.html

Seriously, simple pathfinding should be a non-issue today. There are robust libraries that do it for you. In my case, I can't use the libraries because the input-data I have is already processed (into tiny little tiles, which is the death of A*).

Well, I only remember vanilla ToEE where clicking on an unreachable part of the map would just freeze the game for 2-3 seconds in Homlet.

My conclusion: I did implement tile-to-tile pathfinding yesterday, but will continue optimizing it. What I still have to do is to actually build a "nice" path from the generic path I have now. But in the end, navmeshes should pay off, due to the reduced number of nodes A* has to touch.

 

I would be satisfied if the entire party stayed near each other while moving.

 

All this is very exciting!

I thank you DarkStorm also for giving us some tech infos about the challenges you have ahead of you.

Much appreciated!

Keep it up!