Pathnode Visualization

Discussion in 'ToEE Engine Recreation Project' started by DarkStorm, Jun 12, 2010.

Remove all ads!
  1. DarkStorm

    DarkStorm Established Member

    Joined:
    Oct 2, 2003
    Messages:
    482
    Likes Received:
    1
    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):

    [​IMG]
    [​IMG]

    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 :)
     
  2. Gaear

    Gaear Bastard Maestro Administrator

    Joined:
    Apr 27, 2004
    Messages:
    10,996
    Likes Received:
    23
    I know from reading Agetian's tutorials that nodes are definitely not supposed to be placed in dead sectors (where the sectors contain blocking data), that will definitely screw up pathfinding. But just because the nodes are connected through walls doesn't mean the engine will go through them and try to march you through a wall.

    Drat ... I'm basically talking out of my butt here, sorry. Agetian is the authority on this. I can report to you on application if you want, but I can't really shine any light on the 'science' behind it. :blush:
     
  3. DarkStorm

    DarkStorm Established Member

    Joined:
    Oct 2, 2003
    Messages:
    482
    Likes Received:
    1
    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.
     
  4. Shiningted

    Shiningted I want my goat back Global Moderator

    Joined:
    Oct 23, 2004
    Messages:
    11,729
    Likes Received:
    28
    I'd say their used both for PCs and NPCs.

    And I am surprised to see those links in the Temple: you are right, they shouldn't link through walls like that. But maybe they automatically link to any other pahnode within range, but the engine figures it out when the time comes anyway? Looks weird, for sure.
     
  5. DarkStorm

    DarkStorm Established Member

    Joined:
    Oct 2, 2003
    Messages:
    482
    Likes Received:
    1
    But why pre-generate at all then?
     
  6. GuardianAngel82

    GuardianAngel82 Senior Member

    Joined:
    Oct 3, 2007
    Messages:
    3,475
    Likes Received:
    5
    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.
     
  7. Ranth

    Ranth Established Member

    Joined:
    Jan 26, 2008
    Messages:
    829
    Likes Received:
    0
    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).
     
  8. Gaear

    Gaear Bastard Maestro Administrator

    Joined:
    Apr 27, 2004
    Messages:
    10,996
    Likes Received:
    23
    You could actually remove all the pathnodes from an existing map and you could still navigate, just not beyond (I think) 20 tiles. (This is of course Ag's info, not mine. ;))

    New larger maps like HB (and even WWB, which is not all that large) actually do have pathnodes, btw. Small maps like inside houses don't need them, but outdoor maps of any size really do benefit from them. Laying them out effectively is the challenge - it really does boil down to being an "art," as Ag says, because there's no all-inclusive, common sense methodology that really works across the board.

    (Sorry for wandering OT - I feel like that guy from Inside the Actors' Studio. :biggergri )
     
  9. Ranth

    Ranth Established Member

    Joined:
    Jan 26, 2008
    Messages:
    829
    Likes Received:
    0
    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.
     
  10. DarkStorm

    DarkStorm Established Member

    Joined:
    Oct 2, 2003
    Messages:
    482
    Likes Received:
    1
    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:

    [​IMG]

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

    Shiningted I want my goat back Global Moderator

    Joined:
    Oct 23, 2004
    Messages:
    11,729
    Likes Received:
    28
    There's a quote for the ages ;)

    Pahfinding is meant to be hard; in fact, while bad-mouthing the pathfinding of Command and Conquer once to an engineer, he claimed a good pathfinding algorithm is a holy grail for programmers (don't let that stop you. Normal people should be able to see things folks too immersed can miss).

    The ToEE pathfinding thing does work, though. Using it on the Spider Forest map in KotB (a veritable maze, for anyone who hasn't been there) allows one-click navigation from one end to the other. Without the path nodes, the players could only move in Line-of-sight.
     
  12. DarkStorm

    DarkStorm Established Member

    Joined:
    Oct 2, 2003
    Messages:
    482
    Likes Received:
    1
    Well, not really. Here's an image to illustrate:
    [​IMG]

    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.
     
    Last edited: Jun 16, 2010
  13. Gaear

    Gaear Bastard Maestro Administrator

    Joined:
    Apr 27, 2004
    Messages:
    10,996
    Likes Received:
    23
    That's a does-not-compute moment, right? Different from the venerable old football (American) receivers running their routes feature, which I think is just as irritating to players if not more.

    The party approaches the line of scrimmage ... Tordek flanks out wide left down by Farmer Percy's ... Mialee drops back to pass by Kent's place ... it looks like Tordek is open west of the shared barn ...! Wait, the play is called - ineligible receiver downfield. What the hell was Redgar doing all the way over by Brother Smyth's?! And Krusk never even moved! ... he's going to have to start pulling his weight if he wants to stay on the first squad ...
     
  14. GuardianAngel82

    GuardianAngel82 Senior Member

    Joined:
    Oct 3, 2007
    Messages:
    3,475
    Likes Received:
    5
    I would be satisfied if the entire party stayed near each other while moving.
     
  15. Salk

    Salk Established Member

    Joined:
    Jan 2, 2006
    Messages:
    257
    Likes Received:
    0
    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!
     
Our Host!