|
General Bot Coding See what a pain it is to get those little mechs shooting around
|
|
Roi de France
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
|
improving obstacle detection with trigonometry -
29-01-2004
I am improving my BotWalkPath() function, and for that, I have decided to make the obstacle detection radius vary not only on the bot's speed, but also on the direction. Currently the bot checks for obstacle in front of him, on the left, and on the right. Obviously not behind, since it can't see them.
I want the detection radii (latin, 2nd declination ?) be function of the direction the bot is moving towards. That's to say, if the bot is strafing right, the obstacle detection radius on the right should be greater than the obstacle detection radius in front, and of course even greater than the one on the left, which should be near zero (since the bot is NOT moving left but RIGHT).
A little drawing will help (attached).
The bot is the red thingy.
The RED arrow is where the bot is LOOKING
The GREEN arrow is where the bot is MOVING
The 3 blue dots are where the bot's points of obstacle detection should be : since the bot is moving right, and a bit forward, the detection point on the right should be far away from the bot, and the detection point in front should be closer to the bot (since the bot is moving right MORE than it is moving forward), while the detection point on the left should be very close to the bot.
This is pretty much trigonometry, as seen in the triangle in the bottom right corner of the sketch. I know angle alpha, I know V (it's the velocity of the bot), what I want to know is d, the distance ahead of the bot at which I should put my detection point. If I can do that for the forward point, I will be able to do it for the left and right points as well.
But since I'm legendary good at math, and especially at trigo, gentlemen I beg for your help.
And also feel free to discuss on the idea itself ; is it good, is it bad, what can be improved, etc., etc.
RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
Last edited by Pierre-Marie Baty; 29-01-2004 at 17:33..
Reason: changed thread title to something more relevant
|
|
|
|
|
RealBot Author
Status: Offline
Posts: 3,088
Join Date: Nov 2003
Location: Netherlands
|
Re: improving obstacle detection with trigonometry -
29-01-2004
in very old versions of RealBot i used a simple algorithm that scans around the bot. It fired tracelines ever 15 degrees (or more, you can vary here). and uppon that it reacted how to avoid stuff.
Most logical is to do the opposite, so when you detect something at left, go right. Etc. I bet you can solve this with math. The function itself to fire tracelines would not be difficult for you.
|
|
|
|
|
Roi de France
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
|
Re: improving obstacle detection with trigonometry -
29-01-2004
Thanks but you didn't understand my problem it seems...
The problem is not "how to detect obstacles around the bot", the problem is "how to have the bot worry about obstacles that are closer to it when it's going slow and how to have it worry about obstacles that are further if it's going fast".
That's quite a difference
RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
|
|
|
|
|
Roi de France
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
|
Re: improving obstacle detection with trigonometry -
30-01-2004
Nevermind, it looks like I've found it myself me alone like a grownup
Code:
void BotCheckForObstaclesAtFeet (player_t *pPlayer)
{
// this function returns an integer bitmap describing the presence and quality of any
// obstacle right around the bot. Useful for low walls over which the bot has to jump,
// or for determining if the bot should duck to pass a low ceiling. This function is
// called every frame, systematically, in BotSense(), so that the bot knows, when
// it starts thinking, the quality of the terrain in front of it. First it checks if
// it is about to hit something when walking forward, and if so, it checks if the bot's
// look hits a wall when looking straight horizontally. If so, then the bot might be
// able to duck over something to pass by ; if not, then the bot might be able to
// jump over the obstacle ; we do the appropriate checks.
// NOTE: player's origin is 37 units above the ground (standing height)
// player is 36 units high when ducking
// max stair height is 18 units
// max jump height is 45 units
// max jump height is 63 units when doing a duck-jump
TraceResult tr1, tr2, tr3, tr4, tr5;
Vector v_feet;
float angle_diff, check_distance;
float left_check_dst, front_check_dst, right_check_dst;
pPlayer->Bot.BotBody.hit_state = OBSTACLE_NONE; // first off, reset the hit state bitmap
// given the bot's velocity, bot will check closer or further forward (range 60-120 units)
check_distance = 0.4 * pPlayer->pEntity->v.velocity.Length2D ();
angle_diff = UTIL_VecToAngles (pPlayer->pEntity->v.velocity).y - pPlayer->v_angle.y;
// we gotta transpose this distance to both sides of the bot (and also forward)
// left distance
pPlayer->Bot.BotBody.left_check_dst = check_distance * sin (angle_diff);
if (pPlayer->Bot.BotBody.left_check_dst < 60)
pPlayer->Bot.BotBody.left_check_dst = 60; // bound it to 60 units minimum
else if (pPlayer->Bot.BotBody.left_check_dst > 120)
pPlayer->Bot.BotBody.left_check_dst = 120; // and 120 units maximum
// forward distance
pPlayer->Bot.BotBody.front_check_dst = check_distance * cos (angle_diff);
if (pPlayer->Bot.BotBody.front_check_dst < 60)
pPlayer->Bot.BotBody.front_check_dst = 60; // bound it to 60 units minimum
else if (pPlayer->Bot.BotBody.front_check_dst > 120)
pPlayer->Bot.BotBody.front_check_dst = 120; // and 120 units maximum
// right distance
pPlayer->Bot.BotBody.right_check_dst = check_distance * -sin (angle_diff);
if (pPlayer->Bot.BotBody.right_check_dst < 60)
pPlayer->Bot.BotBody.right_check_dst = 60; // bound it to 60 units minimum
else if (pPlayer->Bot.BotBody.right_check_dst > 120)
pPlayer->Bot.BotBody.right_check_dst = 120; // and 120 units maximum
// get a quick access to these three
left_check_dst = pPlayer->Bot.BotBody.left_check_dst;
front_check_dst = pPlayer->Bot.BotBody.front_check_dst;
right_check_dst = pPlayer->Bot.BotBody.right_check_dst;
// rest of function follows...
RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
|
|
|
|
|
Member
Status: Offline
Posts: 4
Join Date: Jan 2004
Location: alaska
|
Re: improving obstacle detection with trigonometry -
31-01-2004
I think you should have a check for behind the bot if its walking backwards. Most people I know that have played any game for a long time can run backwards and have a good idea of whats behind them and thus avoid it. I am not sure how you would do it though because it would not be right for the bots to have perfect detection of what they can not see. Maybe the check would would only run if they hit something as they where backing up or have it give back false info some of the time so the bot ends up hitting stuff.
|
|
|
|
|
Moderator
Status: Offline
Posts: 403
Join Date: Nov 2003
|
Re: improving obstacle detection with trigonometry -
31-01-2004
PM,
sin, cos, etc. are pretty cpu intensive. There are table lookup methods that are much faster and would work fine here.
For an into, and posssibly some other helpful things check out:
http://docs.mandragor.org/files/Comm....html#fixatan2
http://alleg.sourceforge.net/
or search google for:
"C++ sin table lookup"
Last edited by Austin; 31-01-2004 at 02:57..
|
|
|
|
|
Ex-Council Member
Status: Offline
Posts: 1,090
Join Date: Nov 2003
Location: Canada
|
Re: improving obstacle detection with trigonometry -
31-01-2004
I agree with Austin, replacing the distance functions with look up tables be faster and work just fine.
Seeing that you have 5 TraceResult structs It looks like there's a whole lot more to the function. I assume this function will get called on each frame? If the function does too much, you'll get a lot of lag. You may want to have the function vary how often it checks for obsticles depending on the environment it is in. For example, if the bot is crashing into a lot of things, slow the bot down and do more checks, otherwise, speed up the bot and do less checks.
Maker of the (mEAn) Bot.Admin Manager
"In theory, there is no difference between theory and practice. But, in practice, there is." - Jan L.A. van de Snepscheut
|
|
|
|
|
Council Member, Author of JoeBOT
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
|
Re: improving obstacle detection with trigonometry -
31-01-2004
or you could use your own sin/cos functions using the first parts of the taylor expansion, just as many as you need and not as many as needed for double precision
|
|
|
|
|
Roi de France
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
|
Re: improving obstacle detection with trigonometry -
02-02-2004
thanks guys, and Aspirin you know that already, don't speak chinese when you're talking to me, I have no idea who's your uncle Taylor and what he might have expanded, now no idea, at ALL
RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
|
|
|
|
|
Council Member, Author of JoeBOT
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
|
Re: improving obstacle detection with trigonometry -
03-02-2004
yeah, sorry, just making fun of you
sin x can also be written as the sum over all ( (-1)^n x^(2n+1) / factorial(2n+1) ) for all n from 0 to infinity. here you can just take the first terms to have nice convergence around 0. the bigger your sum gets, the more precise it'll be. just check it out using excel or whatever ...
cos x is the same for ( (-1)^n x^(2n) / factorial(2n) )
|
|
|
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
|
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
Powered by vBulletin® Version 3.8.2 Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com
|
|