Anyone got a raycasting-based navigator working?

[amadmonk]

Looking for an algorithm outline, not a handout here

I'm curious if anyone has a working algorithm for navigation using raycasting (traceline). In theory, you should be able to do stuff with projecting your position forward and raycasting to find collision with ground/water/etc. to look for things like holes in the geometry and even unclimbable slopes. This would be independent of any knowledge from something like a navmesh (although a navmesh would offser superior knowledge in many ways, I don't have working navmesh code at the moment, so that's academic).

I have an idea about how to do this, but it would involve a LOT of raycasting, upwards of a hundred or more rays/frame, and I'm wondering if this is doable without a performance hit.

Anyone got any thoughts?

[mnbvc]

can be done, i'm doing my flying mount navigation this way
YouTube - farming in wow - just the usual stuff (yellow lines = path finding)
i'm casting about 400 rays, this definitely kills your fps if you do it every frame, so after calculating it once i'm only recalculating the position (i'm calculating one position between the start and the end point) every 100 frames. very easy way of navigation and works quite good

[Anonie]

I think that OP means to have a gatherer who can run around to be able to see where the bot is going and if there is something in the path, avoid it. Personally, I don't think it'd be possible without the bot being able to see in 3d. Probably best way is to have it kick in when you actually do get hit an obstacle and jump the thing is half the character's size, or go right/left if it stretches to the left/right (fence/wall).

[BoogieManTM]

I think that OP means to have a gatherer who can run around to be able to see where the bot is going and if there is something in the path, avoid it. Personally, I don't think it'd be possible without the bot being able to see in 3d. Probably best way is to have it kick in when you actually do get hit an obstacle and jump the thing is half the character's size, or go right/left if it stretches to the left/right (fence/wall).

Huh??

nice stuff mnbvc

[amadmonk]

TLDR: roughly how many raycasts (tracelines) per frame can I do without impacting performance -- 1? 10? 100?

I know it's dependent upon my system's performance (quad core i7 w/12 gb ram), but I'm just looking for rough estimates. I know how to use raycasting to "see where the bot is going and if there is something in the path, avoid it" I just was curious whether this was feasible based upon the performance of traceline, since it would imply from 10-100 casts/iteration.

[mnbvc]

a) there is really no need to check it every frame
b) you shouldn't notice the frame drop with 10 casts, but if you use 100 you will definitely notice it

[amadmonk]

Cool... I can probably cache it and only do a "sonar paint" every 50 or 100ms or so. Thanks!

[raindog]

Cool... I can probably cache it and only do a "sonar paint" every 50 or 100ms or so. Thanks!

You can also do some other optimizations, for example, if your raycast determines there is nothing in your path for x yards, and there is nothing else that will cross your path by then, you can just check after the distance you have traveled is close to what you have determined will be safe.