Trace nav - picking route based on distance?

[Lazy]

I thought about traceline nav a while ago but it sounded too complicated, about 20 minutes ago I had an idea to make it much easier ( atleast sound easier :/ ).

The bot fires out 24 tracelines from the head, chest, knees and feet and will choose what distance to travel in based on which trace had the longest distance.
This could be a problem especially when places can be dead ends so the bot would drop waypoints along the way so that the route wouldn't have to be traced all over again.
Should the path turn out to be a dead end the bot will use the waypoints it dropped to travel back down the path marking ones it passes as "dead" so it won't go there anymore.
Fast forward, the bot has already found the hive ( NS ) but was killed by a skulk and is now back where he started.
Now all the bot has to do is follow the waypoints it dropped earlier to get to the hive rather than doing the expensive tracing which was needed before the waypoints existed.

Any huge flaws, ect in this idea?
I haven't slept so there should be a few.

Link to idea image: http://img228.echo.cx/img228/316/tracenavidea4mi.gif

[koraX]

well instead of firing from head, chest and knees, fire tracehull.

Problem with this is that if angles between traces are big, it may skip some important entry (doorways in de_dust2, de_aztec ...).

Also one of earlier racc is doing that, it is firing tracelines ang goes in the direction of longest traceline.

also there are problems with slopes, stairs, pits...

[Pierre-Marie Baty]

If your problem is how to autowaypoint cleanly, I'd advise you to use player motion tracking, and a traceline navigation like in the earliest RACCs.

But if your problem is ALSO pathfinding, instead of marking special waypoints as "dead ends" why wouldn't you just use one of the standard pathfinding algorithms such as A* ?

[Cheeseh]

Thats what my bot does actually when there are no waypoints, I'm sure it's similar to PM's first navigation in RACC bot

[@$3.1415rin]

as does joebotxp ...

has anybody a stable algorithm to detect where it would be useful in terms of waypoint generation to walk to, based on the current waypoint graph and maybe visibility table or something similar ? that'd be pretty cool
When having 2 disjunct graphs for example from the bases in counter strike, one could pick 2 waypoints from different sides of the map, then run A*, which will fail, of course to find any path, but then take the best node from the closed list, since that's the one which's supposed to be the nearest to the enemy. that's anyway sometimes not the case, since there might be a trianglelike structure which prohibits any new paths/waypoints there.

PS: yes, pierre keep on laughing, you don't have such problems. but our approach is quite a lot cheaper to write, I suppose. but we have already enough navmesh threads ...

[Maleficus]

Originally Posted by Lazy

The bot fires out 24 tracelines from the head, chest, knees and feet and will choose what distance to travel in based on which trace had the longest distance.

I don't know how costly traces are in HL, but in the Q3 engine, if 16 bots were in the game and you were doing 384 traces a frame (16 bots X 24 traces) - you would bring the server down to a crawl, even on the fastest computer.

Even if you spread it out over several frames, it can get very costly very quick, and its nearly impossible to design it for EVERY possible scenario of odd map geometry.

If you only had one bot in the map, and it traced around creating a path for all bots to use, it wouldn't be so bad, but you wouldn't be able to play as it learned - in fact it would be best to just let it run around on its own first, create the paths, THEN start the game normally with more bots

One thing though: you have the burden of giving the bot time to "learn" every map, and some maps it will never learn completely (if they have odd geometry or lots of jumps/traps/buttons/doors/etc), unless you use the human player as an unwitting "waypointer" - which would probably be the best best.

A lot of the old Q1 bots worked that way (the Reaper comes to mind): you were encouraged to run around the map at first, and then the bot would get a pretty good layout of where all the paths were for that map. The only hard thing to do there is intelligently lay down waypoints based on where the human moves, then pruning any unneeded waypoints when a complete model of the map was done. Then the burden is on the user.

However, today, most gamers don't want to be the waypointer or have to wait around to play the bots - they just want to fire it up and play, and that may hurt your bot in the eyes of some people if they have to jump thru hoops before they can play. Also, you may never get an optimal path - tho you can usually get one thats good enough, but it depends on how intelligent the human player moved around the map as they created the paths.


Tracelines have a part to play though - depending on your engine, they can help with the environmental sampling of the immediate area around a bot.

[Lazy]

One of the ideas about this system is you would only need to trace once the bot reaches its goal ( longest path ).
The problem I'm seeing now is that maps are getting more and more complex and traceline nav is probably not going to be as effective as it was in the quake1 days where the levels were pretty simple.
And as you said, people don't want to have to make/download waypoints. They want something that works right out of the box and its hard to deliver that when there are so many different custom maps out there.

Theres always the possibility of making the players create the waypoints automatically, but this has a few problems...
- Sometimes inefficient paths
- Purposely making a path into a trap
- Inorder for it to be really accurate there would need to be lots dropped

I have thought about using BSP data for navigation but it seems too complicated mathematically ( yeah, I really hate math ). So I had this idea while thinking up some different navigation methods.

[@$3.1415rin]

and remember that you don't need any real ( tactical ) pathfinding in q1, since it's mostly dm ...

btw, that bsp stuff cannot be that mathematically complicated, pierre implemented one bot using that by himself. and he doesnt like math to much I suppose. also I somehow also like Tub's approach, although that one was really scary, but maybe worth to spent some months on

[Rick]

Tub's approach?