Random Idea for navigation w/o waypoints

[Brainz]

I've had an idea for an alternative bot navigation method (examples are from the game I'm familiar with, Day Of Defeat).

When the bot spawns, it "examines" the texture below it, and looks for points in the distance with the same texture, and heads to it.

I can see texture changes working by sensing the dihedral angle between the two surfaces. if its nearly flat, its a floor, if its around 90 its a wall.

The benefit of this is it would work on any map, especially ones designed for Multiplayer (using a minimum of textures), without waypoints having to be created for them.

Problems I can see occuring is steps into a building, eg on Flashville street in dod_flash, and with routes that require jumps and/or crouchs, or doors.

What do people think, and is it doable?

Thinking about it, some waypoints, eg flags and other objectives, would be needed, but perhaps these could be 'learned' by the bot(s) exploring the first time the map is loaded with the bot.

[Pierre-Marie Baty]

well you know what, you've just discovered the principle of the navmesh

Although navmeshes don't use the floor textures, but simply the triangles they are made of.
Why bothering with textures when bots have access to the whole map data ?

[Brainz]

and I thought it was something new and special.
oh well

How many bots have it implemented?

[botman]

"Why bothering with textures when bots have access to the whole map data ?"

Right. All you really care about is "Can I walk on this surface?". It becomes more complicated when you have surfaces that you CAN walk on but probably don't WANT to walk on (like lava, or water). Then you have the problem of connecting two surfaces that are walkable, but don't have a walkable route between them (such as areas where you have to jump from one surface to another or areas connected by ladders, lifts/elevators, etc.).

Navmeshes are a great way to have the bots be able to navigate on ANY map without having to go to the trouble of placing waypoints for them to use to navigate.

You can find many good links on "navmeshes" or "navigation meshes" by searching for them on www.google.com

Also the "Game Programming Gems" books and the "AI Game Programming Wisdom" books cover this topic.

botman

[Pierre-Marie Baty]

Originally Posted by Brainz

and I thought it was something new and special.
oh well

Don't see it like that eh, be proud to have figured it out yourself while not being a bot coder (and not a coder at all if I understand well)

How many bots have it implemented?

In the Half-Life bot community, AFAIK the only released and working bot featuring this is the official CZ bot from Mike Booth at Turtle Rock Studios. In the works, there's my own bot which I'm still developing, RACC, whose navigation relies completely on a navmesh too. I agree with botman that it's working g-r-e-a-t, even though I'm having a hard time to make my bots walk from point A to point B without using the usual cheating methods like separating view angles and body angles, or applying forward/backwards and strafe speed values that do not correspond to those real players can get with the keyboard alone.
Also the Quake 3 Arena bot is using a sort of navmesh too, although a tridimensional one. Instead of knowing the walkable surfaces, this bot know the navigable volumes. Very useful for rocket-jumping, or when you use a jetpack, or when you navigate into water. But much more complicated, to much for me at the moment 9_9
I don't know about bots for the other game engines. The navmesh concept itself is relatively young in the game industry.

[sfx1999]

Lava is not done by a texture in Half-life like it was in Quake. I've tried it, and it didn't work (at least in Counter-Strike). So go ahead and try it in regular HL.

The best way to know if something is going to hurt you would probably be to look for the trigger_hurt entity. Also, you wouldn't use the view hull at all for this, would you? Clip brushes are invisible, so it would be best to use the player hull.

[Pierre-Marie Baty]

You can use the POINT_CONTENTS() engine call to tell whether a point is in open space, in the void (outside the map), in water or in lava.

And yes, the player hull is mandatory for this. I almost always use the crouched player hull.