.:: Bots United ::.
Page 1 of 2 1 2
Show 40 post(s) from this thread on one page

.:: Bots United ::. (http://forums.bots-united.com/index.php)
-   General Bot Coding (http://forums.bots-united.com/forumdisplay.php?f=24)
-   -   improving obstacle detection with trigonometry (http://forums.bots-united.com/showthread.php?t=568)

Pierre-Marie Baty 29-01-2004 16:25
improving obstacle detection with trigonometry
 
1 Attachment(s)
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.

stefanhendriks 29-01-2004 18:40
Re: improving obstacle detection with trigonometry
 
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.

Pierre-Marie Baty 29-01-2004 18:47
Re: improving obstacle detection with trigonometry
 
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 :)

Pierre-Marie Baty 30-01-2004 10:09
Re: improving obstacle detection with trigonometry
 
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...

red_dots 31-01-2004 00:30
Re: improving obstacle detection with trigonometry
 
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.

Austin 31-01-2004 01:56
Re: improving obstacle detection with trigonometry
 
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"

:|

botmeister 31-01-2004 07:49
Re: improving obstacle detection with trigonometry
 
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.

@$3.1415rin 31-01-2004 11:30
Re: improving obstacle detection with trigonometry
 
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

Pierre-Marie Baty 02-02-2004 19:19
Re: improving obstacle detection with trigonometry
 
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 :D

@$3.1415rin 02-02-2004 23:20
Re: improving obstacle detection with trigonometry
 
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) )


All times are GMT +2. The time now is 08:41.
Page 1 of 2 1 2
Show 40 post(s) from this thread on one page

Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.