Recast / Detour

[Neoptolemus]

SUCCESS!

http://youtu.be/6uFuxnBJfCE

The bot is successfully running around the map. At the moment he just picks random points to visit, and there seems to be an issue with bots sometimes choosing inaccessible areas and just humping the walls (this is probably a consequence of my earlier screenshot with the disconnected islands), but otherwise, as you can see, their movement is pretty smooth.

I want to abstract out some of the movement code to make it easier to order the bot around, and have recovery systems in case the bot falls off a ledge and needs to recalculate etc.

[Whistler]

cool

btw, are you the author of libtess2? I've been using libtess2 in an Android car navigation system for previous company and it works pretty good (no more awkward callbacks with the original GLU tesselator)

[Neoptolemus]

I believe libtess2 is also authored by Mikko Memononen, the same as recast and detour. Luckily, triangulating a Half-Life BSP is a trivial task so I could write my own solution, as I'd rather not include too many third party libraries other than the pathfinding.

Right now I'm writing some code to parse the entities in the BSP, as I'm currently discarding func_wall entities which is not ideal since it means the bots get stuck on fences and railings, the APC in cs_office etc. Will have more updates soon!

[The Storm]

Very very nice progress. I'm impressed!

[Neoptolemus]

I've finished the code to parse entities, so the navmesh generation now takes func_wall entities into consideration. This means bots now avoid the APC in cs_office and other decorative objects that obstruct movement.

I noticed however that the fence in cs_militia is still not being included, which means that it's not a BSP brush entity or a func_wall. Does anyone know what else it might be?

EDIT: Ok so it's a func_illusionary. I assume this is to create the actual chain fence effect and allow bullets to pass through, but what is actually blocking movement? It can't be a BSP brush as I already factor those in. I don't want to include func_illusionary entities either as that will make the bots think they can't pass through, for example, the curtains in cs_747. The mystery deepens...

[The Storm]

Check if the func_illusionary have the FL_WORLDBRUSH flag.

[Neoptolemus]

Hmm that's going to be a little tricky as the flag appears to be set in the edict_t, but navmesh generation happens before that, reading the vertices and entity data directly from the BSP. At this point there is no flag for the entity, just a classname, origin, some rendering info and a pointer into the models array for its bounding box (which is what I read out).

I may need to read in func_illusionary entities, then use off-mesh connections to basically rejoin the broken paths for illusionary objects that allow movement (such as the curtains in cs_747).

Bah!

EDIT: On second thoughts, the engine must know to set that flag from the BSP data so I just need to figure out how it determines whether to set it or not. Time to hit the HLSDK!

[The Storm]

Are you sure of that? I think that in the BSP data you should have flag like SOLID_BSP or something. From what I see the engine does not set this flag but the HLSDK itself, so it should be read directly from the BSP.

Edit: Also from this old post of PMB - http://forums.bots-united.com/showthread.php?t=1226 he says that the mappers are responsible for the flag, so a little bit of research will be good. Just dump out the entity properties out of the BSP data - one from cs_747 and one from cs_militia and compare them to see what makes them solid.

[Neoptolemus]

Yeah, the entities section is all ASCII so you can open it up, scroll to that bit and take a look. However, it may be that the flag is set in the model reference. In fact, thinking more about it, that would make more sense anyway. I'll take a look tonight.

In the meantime I've decoupled the bot's movement from their view, so they can strafe, run backwards while looking at something. I have made it so that running backwards is less accurate (so they're more likely to miss the door and run into the wall when not looking where they're going).

I need to figure out a way to stop Detour from hugging corners so tight, as bots often get caught on geometry. Are HL collisions done with boxes or cylinders? I wonder if that's the issue.

[SamPlay]

Hi,
Half-life does not handle collision the same way than Quake.
It is POINT based, and move computations -like traces- are at least partly performed in hull-specific clip-bsp trees , which are basically pre-computed "hull-based inflated " worlds ( called "configuration spaces" in robot path planning; see zhlt code for details).
If the way recast computes contours away from walls is different than the bsp builder inflation/bevelling method, it may be closer in some occasions; to me, all this is the most obvious explanation for your bots unexpectedly bumping into the visible world.
I hope this helps.