Pathfinding Routine

[Legacy_henesua]

               I've been working on a pathfinding routine in JavaScript for a tilebased game that I am writing in JavaScript. I am fairly proud of the pathfinding I came up with as I haven't done much with JavaScript for the past 13 years, and yet here I've made a few modifications to the standard A* search.

The pathfinding code is available on my pastebin.

Other than this code (which doesn't really belong on this forum), I wanted to share a thought I had while writing the code. I had this thought - which I'll describe in a minute if you can bare with me -  because I am thinking a lot about tiles and grids. Between my current project, and the improvements to Seamless Area Transitions which I released for NWN awhile back, you could say I've got squares on the mind. Since NWN is more or less a tile based game despite the 3D illusion, these square thoughts occassionally turn to elipses orbiting around NWN. Incidentally the thought I am about to share relates to an idea I had while I was still working on Arnheim but never got around to implementing.

I like frameworks in NWN which create relations between areas. Seamless Area Transitions does this as the tag describes coordinates within a grid of other areas/nodes. Rolo has a regional mod project which takes a different approach but is yet another framework which positions areas at coordinates on a grid.

So the thought I had was pathfinding for creatures in NWN through a grid of areas. Using an A* routine and a function which could determine whether passage was possible between two adjacent tiles, you could provide a start and end destination point for a creature and have it wander through some areas. The actual implementation would take some finesse, as you'd have to treat the routine that simulates movement of the creature differently when a PC is in the same area as the creature - in that case you'd have to switch over to influencing the creature's AI until it perceives the PC and then determine whether or not to suspend the routine and later if the creature survives the encounter with the PC whether or when to resume the path finding routne driving its movements.

Anyway, its an idea. One of the germs of the idea came from a wolf pack I created which was designed to roam through a forest in Arnheim. My implementation was limited to movement thorugh one area but ti looked very cool when a PC witnessed it as the pack of wolves naturally roamed across the area with a modified patrol script. Another influence was the old Atari game "Adventure". The movement of the creatures in the game from "room" to "room" and the way they could perceive the player in adjacent rooms and thus follow the PC was very cool. The roaming of the bat was also interesting, albeit random.

It would be very cool to create the same behavior for a flying dragon in NWN. The dragon would move around overhead. A text message would popup for players in the area when the dragon was spotted overhead. And then if the dragon spotted a PC in the area it might land.

Just an idea. Enjoy.

lastly - I've been looking at roguelike games a lot too and discovered this amazing roguelike toolkit written in javascript. its a very nice implementation, and the pathfinding in rot.js was used as a base to write my own.
               
               

               

                     Modifié par henesua, 21 juin 2013 - 04:42 .
                     
                  

            

[Legacy_Squatting Monk]

               This system uses a grid-based method like you described. I haven't used it very much, but the demo was slick.
               
               

               
            

[Legacy_henesua]

               Can you describe how it works? The Vault page has no information, and suggests to me that it only deals with pathfinding within an area. While that is interesting, my idea was to generate a pathfinding for creatures that roam across multiple areas.

Example:
A particular wolf pack is not currently summoned in any area, but you simulate the pack's location in a script. It roams across multiple areas in a wood region looking for PCs and can detect PCs in adjacent areas. You'd also give the pack a few destinations it likes to go to at particular times, and at others it moves a little randomly. So you'd generate paths through the wood between typical points with a little randomness thrown in.

Then lets say the wolf pack while en route to a watering hole, crosses a ridge, and from this ridge they are able to spot whether PCs are present in a number of adjacent areas. If they spot a PC, run a script to generate a path from the ridge to the PCs location. Then simulate this movement via script. If no PCs are in the intervening areas the wolf pack is not created in those areas, but a script tracks their movement through those areas. Then the pack arrives in the area of the PC, and if a PC is in the area the wolf pack is created. Then they are given the PC as an attack target, and the standard pathfinding takes over.


Another example is to do the same thing with flying creatures like dragons that follow paths through the module, but will spawn on the ground if they spot a target while flying overhead.

Paths plotted in this way would involve a number of nodes, and a time interval spent at each node.
               
               

               
            

[Legacy_henesua]

               I rolled up my sleeves with a text editor and looked at the module to find the scripts and found this snippet which confirms it for me:

if (GetArea(oStartNode) != GetArea(oTargetNode))
       {
    // debug
    SendDebugMessage("FindPath(): areas differ", SERVER_SYSTEM_AI_PATHFINDING);

    DestroyObject(oPathNodeArray);
    DestroyObject(oUncheckedNeighbours);
    SetLocalInt(oPathOwner, AI_PATH_SEARCH_DONE, TRUE);
    SetLocalInt(oPathOwner, AI_PATH_SEARCH_RESULT, bPath);
    return;
       }

That pathfinding project is for AI within an area, and sends a creature between waypoints. While that is cool, its not what I was discussing above as I am interested in the idea of having creatures roam between multiple areas. So in some respects you can think of each area as a node in the path - although in my Seamless Area Transitions I allow for a more fine grained grid, and would likely use that.

One trick would be to provide more information about the connectivity between nodes and to use that information with the pathfinding routines.

Another cool idea would be to track the movement of players through the module from "node" to node" and build up a database of paths. You'd want to favor the most recent information, as the module will change over time.
               
               

               
            

[Legacy_Squatting Monk]

               Ah, I see what you're saying. The closest thing to that I know of is the landmark routines from MemeticAI. It allows you to create a series of trails between landmark waypoints, and allows the NPC to figure out the best way to get from point A to point B using the trails. There are also gateway landmarks, which are set on the area transitions, and the builder can define which gateway points to which other one.

It's supposed to be able to handle moving creatures across area transitions (I only ever got it working for intra-area pathfinding), but I think it does this by setting their AI level higher and letting them actually walk there. As long as there's a path in the network of trails that gets there, though, the NPC should be able to trace it.

The way you describe it seems less resource intensive and more flexible, but a little more complicated to set up.
               
               

               

                     Modifié par Squatting Monk, 23 mai 2013 - 01:24 .
                     
                  

            

[Legacy_henesua]

                For those interested in pathfinding in general I followed a link recently to an amazing website:

Amit Patel's Red Blob Games is chock full of great resources for game developers, and since I am particularly interested in pathfinding recently his pathfinding section has proven valuable.

Thanks, Amit!