.:: Bots United ::.  
filebase forums discord server github wiki web
cubebot epodbot fritzbot gravebot grogbot hpbbot ivpbot jkbotti joebot
meanmod podbotmm racc rcbot realbot sandbot shrikebot soulfathermaps yapb

Go Back   .:: Bots United ::. > Developer's Farm > General Bot Coding
General Bot Coding See what a pain it is to get those little mechs shooting around

Reply
 
Thread Tools
improving obstacle detection with trigonometry
Old
  (#1)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
Default 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.
Attached Thumbnails
Click image for larger version

Name:	Sans titre.png
Views:	421
Size:	3.0 KB
ID:	52  



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
  
Reply With Quote
Re: improving obstacle detection with trigonometry
Old
  (#2)
stefanhendriks
RealBot Author
 
stefanhendriks's Avatar
 
Status: Offline
Posts: 3,088
Join Date: Nov 2003
Location: Netherlands
Default 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.


Author of RealBot, "Arrakis" and "Dune 2 - The Maker" | co-Founder of Bots-United | Fundynamic | Blog | E-Mail me
  
Reply With Quote
Re: improving obstacle detection with trigonometry
Old
  (#3)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
Default 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."
  
Reply With Quote
Re: improving obstacle detection with trigonometry
Old
  (#4)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
Default 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."
  
Reply With Quote
Re: improving obstacle detection with trigonometry
Old
  (#5)
red_dots
Member
 
Status: Offline
Posts: 4
Join Date: Jan 2004
Location: alaska
Default 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.
  
Reply With Quote
Re: improving obstacle detection with trigonometry
Old
  (#6)
Austin
Moderator
 
Austin's Avatar
 
Status: Offline
Posts: 403
Join Date: Nov 2003
Default 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..
  
Reply With Quote
Re: improving obstacle detection with trigonometry
Old
  (#7)
botmeister
Ex-Council Member
 
botmeister's Avatar
 
Status: Offline
Posts: 1,090
Join Date: Nov 2003
Location: Canada
Default 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
  
Reply With Quote
Re: improving obstacle detection with trigonometry
Old
  (#8)
@$3.1415rin
Council Member, Author of JoeBOT
 
@$3.1415rin's Avatar
 
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
Default 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


  
Reply With Quote
Re: improving obstacle detection with trigonometry
Old
  (#9)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
Default 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."
  
Reply With Quote
Re: improving obstacle detection with trigonometry
Old
  (#10)
@$3.1415rin
Council Member, Author of JoeBOT
 
@$3.1415rin's Avatar
 
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
Default 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) )


  
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump



Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com