In games like half-life, they use something called info nodes that you put on certain places on the level and this makes it easier for the enemies to navigate throught the map. I want to have something like this in my game, but I can''t figure out how they work. Does anyone know how they work or an arctile that explains them? ------- Me Hardguy. and here is my game...

I''d really be interested as well, but since I never found any article neither, here''s the explanation I came up with (though I''ll have to go and read the SDK 2 source code now that it comes with enemy AI).

The nodes just serve as the "tiles" you would have in a tile-based game. By having tiles, you can much more easily make A* algorithms work. I mean, HOW would you implement A* in a game like Half Life ?

Not to be offensive, but if you don''t see why they use something, maybe that''s a good sign that you don''t need it ? First choose your task, THEN choose your tools !

youpla :-P

Each info node has a list of the nearest accessible nodes around it.
If some monster "want" to go in a particular direction, path-finder is looking for a nearest node on its way.

I sat up all night and came up with an pathfinding algoritm using info_nodes. It should be faster than using A* and you can use it in any sort of environment, it is kinda complicated but if anyone wants to know more might I''ll write a little doc on it.

I must also say that it is not fully implemented yet, so I am not 100% sure that it will work....but it should.


-------
Me Hardguy.
and here is my game...

Its a very interesting method and I can see that it would be very useful. I would use it, except that I use randomly generated maps for my RPG. It would be very usefull to use them, if I could find a way of doing so. I think the way I could do it is through towns (which are defined specifically at a location) and through special locations (such as caves or whatever the quest locations are). Anyway...

It should work, and I think if you can set up a general grid for nodes to be placed on then the following is possible:

Grid:
_______
|_|_|_|
|_|_|_|
|_|_|_|

Basically, you use your pathfinding algorithm from the destination (yes, destination) to find out either the closest node or all the surrounding nodes (in that sqare). Then, use your node pathfinding to work its way back to the source node and to the location of that monster. Just theoretical, but I think that it would work.

-Chris Bennett ("Insanity" of Dwarfsoft)

Check our site:
http://www.crosswinds.net/~dwarfsoft/
Check out our NPC AI Mailing List :
http://www.egroups.com/group/NPCAI/
made due to popular demand here at GDNet :)

Sounds interesting. So these nodes are basically like a grid, except don''t have to be in a grid formation... That would make skewed formation easy to navigate... Cool!

Has anyone considered a more realistic pathfinding algorithm? I read in an MIT doc someplace on their server, about an algorithm that works more closly with what was closer to the person and cared less about what was farther away until the guy got there.
That sort of thing would be extremely realistic, and would help when an NPC is exploring an area he knows nothing about. (wish I could find that page again...)

Yes, the idea is to get a grid on a non grid-based system.
Hence you canuse a classic A* on a ploygonal world.
When your units are not on a info-node, they just try to go to the nearest.

Those info-node are really used as waypoints. Look at a bot like Jumbot for Halflife to see much better how they can effectively be used !

There are two other good ideas that I''d like to have opinions on, while we are at it :

On an automatically generated map, have a sort of automatic waypoint placement (especially buildings, resources, crossroads, would have a linked waypoint/info node)

On a polygonal map (non grid based), how do you decide what is and what isn''t a waypoint. This problem is very important for Bots, for instance... if you look at the automatic placement of nodes in Jumbot, sometimes it just get totally mad ... and jsut can''t do as good as hand made placemement.

Any thoughts ?

I haven''t seen Jumbot, but for what I know, all the bots do something like this:
1) when there are no waypoints in level, they just run to closest items and players and use some simple short-range-knowledge to dodge bullets and to not to drop in lava / off ledges.
2) they drop waypoints below them all the time and I believe they drop waypoints even where the other players (humans, maybe) are. F.I if you rocket jump, the bot AI will place there a rocket-jump-waypoint so that the bots can RJ in that point, too.
3) after the whole level has filled with waypoints, the bots can navigate there easily

So I can''t see how Jumbot can get "mad" as you said, since more waypoints means always a better route (but slower to search). Maybe there''s just some bug in Jumbot, but generally the bot AI described above, should work.

-Hans