Rekindled Phoenix's Blog

An interesting approach .. what sort of speed are you getting for plotting paths over reasonable distances?

I've tried doing this in the past but I failed. The problems I encounted is: -

 

1) Performance over a long distance

2) Complicated enviroment with dead ends - you'll search down a dead end and have to come back

3) Complicated enviroments with stairs door etc.

 

You said :-

 

Some high-budget games use static node path meshes, which must be a final step in production for each map. I wanted a different approach that didn't require a web of objects hand placed into the world.

 

Hand placing is an old fashioned approach which no current games do.

 

.... Just trying to save you going down blind alleys.

..i found that Djikstra, i have implemented with some small optimizations, working beautifully fast .. it was easy also to make it tied to game logic in such sense that it can enable/disable search nodes depending on accessibility of specific zones (door open or not, etc) ... I highly recommend..

The most optimum setting would be for a collection hash values (start / end) to be stored for future lookup. Pre-caching the values in a map also works in comparison to my on-the-fly method.

 

An interesting approach .. what sort of speed are you getting for plotting paths over reasonable distances?

Instantaneously for 50 LE Units. I don't need anything past what my camera can see so I haven't tried.

 

I've tried doing this in the past but I failed.

1) Performance over a long distance

2) Complicated enviroment with dead ends - you'll search down a dead end and have to come back

3) Complicated enviroments with stairs door etc.

 

Hand placing is an old fashioned approach which no current games do.

Actually, Fallout 3 and Unreal do. Those aren't necessarily the latest and greatest, but they are still popular in gaming communities.

 

This problem can easily be solved by placing collision data keys on certain objects. If a loop returns a collision key of 'stairs', the algorithm I'm using can be tweaked to adjust height. Changing the radius of the circular checks allows small rooms and narrow passageways to be searched. When an entity exists over a far distance, the radius increases dramatically to save node data.

 

..i found that Djikstra, i have implemented with some small optimizations, working beautifully fast .. it was easy also to make it tied to game logic in such sense that it can enable/disable search nodes depending on accessibility of specific zones (door open or not, etc) ... I highly recommend..

Exactly! This was a similar approach I used to avoid the rocks in the picture. Each avoided model is stored with a minimum node radius in a collection.

I believe a few games use similiar to what you are doing ie character controller points of accessibility/expansion. But they do it offline to build a navmesh from the results.

 

Good example with FO3 and Unreal, however I beleive FO3 was a semi-auto/semi hand drawn navmesh. Unreal/UDK has now abounded waypoint graphs for nav meshes.

 

Check out:-

http://www.ai-blog.net/archives/000152.html

 

 

Hope this helps.

 

Chris

Everything I've read says a NavMesh is the way to go.

Anything is acceptable if it works for your game but the reasons for using navmesh over anything else seem quite compelling. If I were starting out at the beginning with the hindsight I now have I'd be using a navmesh system from the word go. However, I have implemented an abstraction layer in my AI allowing me to swap fairly painlessly in the future should I need to.

@Rick

I agree with you, NavMesh is a quick way of doing things for all games. If you utilized my method and pre-calculated all of the data, it would be the equivalent of a navmesh without any hand placed nodes. I was just happy to share my solution to the rest of the community.

 

@Pixel

My AI follows a collection of vectors. That way if I ever need to I can swap to another method.

I can confirm that FO3 use navmesh.

 

This apporach can work with NPC that have near and small re-spawn area.

Also it could work with an accurate game design, however i feel this will take more and more work for the designer wich need to avoid maze or complicated area like bridge and river.

 

I did something similar in past, it worked but not as well as i hoped.

 

Anyway happy to see there are other "open" mind wich doesn't have fear to try new way!

 

Good job.