Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / Best way to find all objects within a given radius?

Author
Message
QuothTheRaven
21
Years of Service
User Offline
Joined: 2nd Oct 2002
Location: United States
Posted: 18th Mar 2006 21:45
I'm trying to create a grenade-type blast effect, and I want to find all the objects within the blast radius of the grenade. Now the stupid way to do this would be to cycle through every object and check the distance to the grenade, and this would obviously be time consuming if there are a huge number of objects, so it's not an option. Can anyone think of a quick way to find all objects near a given object?

I'm using Newton as well if that helps.

Lukas W
20
Years of Service
User Offline
Joined: 5th Sep 2003
Location: Sweden
Posted: 18th Mar 2006 21:57 Edited at: 18th Mar 2006 22:02
i made this in newton once.. let me see if i can find the source.

edit.
i check all objects in the scene.. maybe that isn't very smart :/ here is my source anyhow. it will give the objects a kick; the closer to the hit, the harder the kick.

ps. it uses some types and arrays that are not included with this little snippet, but you probably get the point :/


HorizShootiz - finished
Pheonixx
20
Years of Service
User Offline
Joined: 6th Oct 2003
Location: Columbus, Ohio
Posted: 18th Mar 2006 22:14 Edited at: 18th Mar 2006 22:15
every 'character' 'prop' whatever in your game should have a current sector value. When you are checking for an area of affect, all you have to do is check if they are + or - sectors from you. Running a SQRT distance check is extremely slow, as is checking all actors against it.

if i'm two grids/sectors away, I take 25% damage, if I am one grid/sector away I take 75% damage, if I am on the same sector, i'm toast.


mmmmmmm.... jelly.....


if myx < thierx+2 and myx > theirx-2
if myz < theirz+2 and myz > theirz-2
print "you got hosed tommy!"
endif
endif

http://ausukusa.breakset.com
QuothTheRaven
21
Years of Service
User Offline
Joined: 2nd Oct 2002
Location: United States
Posted: 18th Mar 2006 22:17
Quote: "every 'character' 'prop' whatever in your game should have a current sector value. When you are checking for an area of affect, all you have to do is check if they are + or - sectors from you. Running a SQRT distance check is extremely slow, as is checking all actors against it.

if i'm two grids/sectors away, I take 25% damage, if I am one grid/sector away I take 75% damage, if I am on the same sector, i'm toast."

Er...sorry, but that doesn't sound like something I would want to use at all. That means I would have to update the sector for every object in the game and...ew.

Agent Dink
20
Years of Service
User Offline
Joined: 30th Mar 2004
Location:
Posted: 18th Mar 2006 23:00
Just make an invisible collision sphere appear with your explosion at the damage radius you want, and anything that collides with it gets damaged?

www.badpicsofmatt.tk
www.silver-dawn.net
Pheonixx
20
Years of Service
User Offline
Joined: 6th Oct 2003
Location: Columbus, Ohio
Posted: 18th Mar 2006 23:04
you are doing it already. every object contains location information, all you have to do is divide that objects location by a grid size, and store it into a variable. not many things move every single turn, and when they do move, you just store what grid they are on. There is going to be a lot of situations where you need to know where 'a' is in reference to 'b' and a simple grid comparisson is a lot faster then throwing out distance equations all over.

int(object position x(id) / 100) = this objects x grid if each grid is 100 wide.

http://ausukusa.breakset.com
CuCuMBeR
21
Years of Service
User Offline
Joined: 11th Jan 2003
Location: Turkey
Posted: 18th Mar 2006 23:22 Edited at: 18th Mar 2006 23:23
i think your solution is finding the area(or volume) of blast and check which objects are in the area..still i think you have to cycle through every object though.
but maybe you can make a collision sphere for this area(or volume) and check which objects does it collide with, this way you will check only some objects i guess.
sorry my english is not good enough to explain

EDIT: by the way if you achive this, let me know too
GatorHex
19
Years of Service
User Offline
Joined: 5th Apr 2005
Location: Gunchester, UK
Posted: 18th Mar 2006 23:23 Edited at: 18th Mar 2006 23:24
I would turn the granade object into a sphere

wrap explosion image on it

set ghost on

grow sphere bigger each sync (keep it fast like 5-10 syncs max)

increase fade value as it grows until explosion sphere dissapears

anything caught in the sphere would take damage = to the fade value so if you was close u take high damage and you at the edge not much.

If a players camera was caught inside the explosion he will get a nice see through explosion/fire effect flash on his screen.

CuCuMBeR
21
Years of Service
User Offline
Joined: 11th Jan 2003
Location: Turkey
Posted: 18th Mar 2006 23:25
yeah i tried to say somethin like what GatorHex said..
Pheonixx
20
Years of Service
User Offline
Joined: 6th Oct 2003
Location: Columbus, Ohio
Posted: 18th Mar 2006 23:59
if you do not parse your objects, you are essentially checking every single object against a range or collision. That is slow and noobish. If the collision functions automatically parse objects for you, then whatever.

http://ausukusa.breakset.com
GatorHex
19
Years of Service
User Offline
Joined: 5th Apr 2005
Location: Gunchester, UK
Posted: 19th Mar 2006 00:08 Edited at: 19th Mar 2006 00:08
Pheonixx,

if its something like a quake death match there aren't that many objects, but i agree your method is best for something like a mmorpg style game with hundreds of players and monsters.
QuothTheRaven
21
Years of Service
User Offline
Joined: 2nd Oct 2002
Location: United States
Posted: 19th Mar 2006 00:29
Quote: "grow sphere bigger each sync (keep it fast like 5-10 syncs max)

increase fade value as it grows until explosion sphere dissapears

anything caught in the sphere would take damage = to the fade value so if you was close u take high damage and you at the edge not much."

Well...this would work except I have no way to know what the sphere is colliding with except by going through every single object and checking collision, which is exactly what I want to avoid.

CuCuMBeR
21
Years of Service
User Offline
Joined: 11th Jan 2003
Location: Turkey
Posted: 19th Mar 2006 00:44
dim the objects positions which will be in the area of explosion just before it occurs (still ull have to run through every dynamic object though but position recording might be faster than collision calculation in this case)
then run the collision calculation through these dim objects..
no other idea..
GatorHex
19
Years of Service
User Offline
Joined: 5th Apr 2005
Location: Gunchester, UK
Posted: 19th Mar 2006 01:09 Edited at: 19th Mar 2006 01:19
some rough code becuase a colision returns the object number it hit, I've dont it like this before..

if colision(sphere) > 0 then do_damage_procedure(colison(sphere))

procedure do_damage_procedure (playerID)
dim player_health(playerID) = player_health(playerID) - damage
return

there we go we only did one collison test no matter how many players are online. You may have to work on th code to damage multiple players in the radius but the theory is sound. It will work real well as it is for bullets!

I gota go to sleep now i cant even type straight -.-
QuothTheRaven
21
Years of Service
User Offline
Joined: 2nd Oct 2002
Location: United States
Posted: 19th Mar 2006 02:14
Quote: "You may have to work on th code to damage multiple players in the radius but the theory is sound."

Yeah...see that part which you didn't say anything about is the question I'm asking. Your code only works for one object, because the collision command will only return one object of collision.

Green Gandalf
VIP Member
19
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 19th Mar 2006 02:24
How many objects are you talking about? Calculating a few hundred, or perhaps even a few thousand, distances shouldn't take much time (you don't need the square roots of course).

But I agree it would be nice to avoid the check through all objects in some elegant way.
david w
18
Years of Service
User Offline
Joined: 18th Dec 2005
Location: U.S.A. Michigan
Posted: 19th Mar 2006 02:31
assinging the objects a type id and then only checking for objects of a given type would speed things up. Just a thought.
Green Gandalf
VIP Member
19
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 19th Mar 2006 02:37
Yes, and changing the type id as necessary whenever an object moved would avoid searching through the list. Perhaps the type id could be the sector numbers suggested by earlier posts?
david w
18
Years of Service
User Offline
Joined: 18th Dec 2005
Location: U.S.A. Michigan
Posted: 19th Mar 2006 04:52
That is how I do it. Why check rocks/trees/buildings/crates/whatever if you dont have to.
dark coder
21
Years of Service
User Offline
Joined: 6th Oct 2002
Location: Japan
Posted: 19th Mar 2006 11:19
well checking say 1k objects distance shouldent make any noticable lag, one other method would be to check it over a few frames as grenades take time to explode so in that time you could be checking everything.

Halowed are the ori.
GatorHex
19
Years of Service
User Offline
Joined: 5th Apr 2005
Location: Gunchester, UK
Posted: 19th Mar 2006 13:41 Edited at: 19th Mar 2006 13:45
if you have any sense you group your object numbers by type

sliders 1-100
players 100-200
scenery 1000-2000

then you can reduce the number of items you need to itterate for a given test.

I thought about the sphere explosion if it was in the slider group it would push the player aside or up in the air i.e. fake newton style

Now I've had some sleep I see that you can handle a multiple player sphere hit by setting the colision off on an object after it has taken damage until the explosion ends. Then it dont report its object ID more than once.

Lost in Thought
20
Years of Service
User Offline
Joined: 4th Feb 2004
Location: U.S.A. : Douglas, Georgia
Posted: 19th Mar 2006 13:59 Edited at: 19th Mar 2006 14:00
I would go with keeping up with the player sectors. If you do this then you may not have any checks when it explodes and no one is around. Like he said you already need ot keep up with where the player is in 3D space. All you have to do is apply that to a larger scale 3d grid (sort of like making a ghetto octree system) and store a list of objects in each sector. And there is no need for fancy maths for this. You can just simply compare the min/max of each sector to your object's position at startup. Then you only need to check it against a max of 3 sectors when moving.

[edit] You could even get fancy and keep up with which sectors have walls in them to keep the blast from killing people through walls. Something you can't do with sphere collision without ray casting as well.

GatorHex
19
Years of Service
User Offline
Joined: 5th Apr 2005
Location: Gunchester, UK
Posted: 19th Mar 2006 14:35
you could use the static line of sight command to see if there was a wall in the way btween the granade and the player hit
Pheonixx
20
Years of Service
User Offline
Joined: 6th Oct 2003
Location: Columbus, Ohio
Posted: 19th Mar 2006 16:51
If things like crates, sandbags, or partial walls are objects in that sector, you could do a generic 'reduce damage for this sector by x% to similute partial cover'.. I really like terrain features when they are reactive. You can also 'reduce damage per target by x% depending on the stance of the target'.. such as your enemy is in a foxhole, fast freddy, prone, crouched, upper stance, or just running like away scared. All of this stuff doesn't slow down your program enough to merit not having it, and it's a standard I expect when I play an FPS or any other style combat game.

http://ausukusa.breakset.com
Philip
20
Years of Service
User Offline
Joined: 15th Jun 2003
Location: United Kingdom
Posted: 20th Mar 2006 00:00 Edited at: 20th Mar 2006 00:01
If you want to calculate a lot of distances and compare to a pre-set distance, the answer is to use pythagorean maths to calculate the length of the vector from the starting position to the position to be checked.

But what you do NOT do, is sqrt the result. Instead you check against the ^ figure. This avoids any need for lots of vector lengths or, god help you, sqrts. Its just a bunch of multiplication calcs which go faster than crap through a goose (to quote General George S. Patton).

Cheer if you like bears! Cheer if you like jam sandwiches!
Quote of the week: "... I started learning DBP while I was a Satellite Network Controller for the US Army Space Command ... "
Pheonixx
20
Years of Service
User Offline
Joined: 6th Oct 2003
Location: Columbus, Ohio
Posted: 20th Mar 2006 00:09
there is always the ABS(x1-x2)+(z1-x2))
similar to what philip suggested but no multiplication needed.

I wonder how long it will take for someone to make yet another benign program to demonstrate which of these methods is faster?

http://ausukusa.breakset.com
Philip
20
Years of Service
User Offline
Joined: 15th Jun 2003
Location: United Kingdom
Posted: 20th Mar 2006 00:28
Avoid the use of abs(). Its very slow.

Cheer if you like bears! Cheer if you like jam sandwiches!
Quote of the week: "... I started learning DBP while I was a Satellite Network Controller for the US Army Space Command ... "
Pheonixx
20
Years of Service
User Offline
Joined: 6th Oct 2003
Location: Columbus, Ohio
Posted: 20th Mar 2006 00:32
really? all it's doing is removing the sign, and I would think it would be faster to say..

if value is < 100

then to say...

if value is > -100 and value is < 100

how slow could it possibly be? (I'd test it since you brought it up, but I don't have my dev computer)

http://ausukusa.breakset.com
re faze
19
Years of Service
User Offline
Joined: 24th Sep 2004
Location: The shores of hell.
Posted: 20th Mar 2006 01:36
shouldnt abs just set the leftmost bit to 1? should be quite fast.

Baggers
19
Years of Service
User Offline
Joined: 31st May 2004
Location: Yonder over dem dere hills
Posted: 20th Mar 2006 12:56
What it should do and what it does in DBP can often be quite different. I havnt speed tested the command, however by the size of Philips current project I'm pretty sure he's covered nearly every bugquip that could exist in DBP. He's a wise bear to listen to....however if your doubting just speed check the command yourself.

M.I.A is pending
Lost in Thought
20
Years of Service
User Offline
Joined: 4th Feb 2004
Location: U.S.A. : Douglas, Georgia
Posted: 20th Mar 2006 13:39 Edited at: 20th Mar 2006 14:08
Quote: "shouldnt abs just set the leftmost bit to 1? should be quite fast."


No it has to change almost every bit as negative values use two's compliment method of represnting numbers.



But still all it should do is:



Which shouldn't be too terribly slow.

[edit2] Holy jehuzzle Batman! Why is ABS slower than that DBP function?



Pheonixx
20
Years of Service
User Offline
Joined: 6th Oct 2003
Location: Columbus, Ohio
Posted: 20th Mar 2006 17:42
Quote: "Holy jehuzzle Batman! Why is ABS slower than that DBP function?"


Could you post the results for me? I'm interested in the results. (dev computer is off a few miles )

http://ausukusa.breakset.com
spooky
21
Years of Service
User Offline
Joined: 30th Aug 2002
Location: United Kingdom
Posted: 20th Mar 2006 17:56
I recently played around with a code snippet and simply moved 3 ABS commands around and it nearly doubled the frame rate. ABS should be an almost instant command.

http://forum.thegamecreators.com/?m=forum_view&t=74154&b=6

Boo!
Philip
20
Years of Service
User Offline
Joined: 15th Jun 2003
Location: United Kingdom
Posted: 20th Mar 2006 17:58
Yeah, I was also using the ABS command a lot and I lost an awful lot of FPS.

Given that I've got a 35k line project, that took a while to find.

Cheer if you like bears! Cheer if you like jam sandwiches!
Quote of the week: "... I started learning DBP while I was a Satellite Network Controller for the US Army Space Command ... "
spooky
21
Years of Service
User Offline
Joined: 30th Aug 2002
Location: United Kingdom
Posted: 20th Mar 2006 18:08
Wow. Just used Lost's ABS replacement on that blobs code snippet and frame rate jumped by factor of 4!

Unfortunately posting the fact that ABS is dead slow will get rejected as a bug but maybe Lee may find a silly coding error and fix it for next update.

Boo!
Pheonixx
20
Years of Service
User Offline
Joined: 6th Oct 2003
Location: Columbus, Ohio
Posted: 20th Mar 2006 18:41
Project One is only 10k lines. I've been having a terrible time finding out why it's running so slow, and I use the ABS() probably a hundred or so itterations per loop with all the different players and such. This information is very suprising! ABS is supposed to be fundamentally fast

http://ausukusa.breakset.com
RiiDii
19
Years of Service
User Offline
Joined: 20th Jan 2005
Location: Inatincan
Posted: 20th Mar 2006 18:43
The method I recently tried worked quite well. I kept an array of the 100 (could be more, easily) closest objects to the player. Any objects outside of this range get left out of any player-related checks or calcs (for example, the player cannot target objects not on this list, or, in your scenario, grenades cannot possibly reach that far). Also, the list only updates by 1000 objects per cycle. This means in 10 frames (at 60 FPS, 1/6th of a second), the list can be updated with 10,000 objects - which was more than enough, even to check for trees and rocks and whatnot. Then checking the list is a very quick For i = 1 to 100 loop. The distance (actual distance) is stored in the array (along with the Object ID), and is calculated using vectors (very fast). So, the oldest a distance calc can possibly be is 10 frames old, which is close enough the player will not be able to tell the difference - especially if the grenade takes more than 10 frames from launch to explosion.

Here's the functions.



Open MMORPG: It's your game!
spooky
21
Years of Service
User Offline
Joined: 30th Aug 2002
Location: United Kingdom
Posted: 20th Mar 2006 19:02
I have posted the ABS 'bug' in bug forum but Lee will probably reject it as not being a bug but a 'future optimization'. I'm hoping though that it's fairly simple to fix.

I've also warned him I'll be updating to next beta and recompiling all my old code.

Boo!
Milkman
18
Years of Service
User Offline
Joined: 30th Nov 2005
Location: United States
Posted: 20th Mar 2006 19:46
Back to the explosion problem, you could use raycasting. That way when you hit something in Newton, you could get the object hit, check if that object is static or dynamic, and react accordingly.
You would have to do at least 64 raycasts per explosion though

formerly xMik
QuothTheRaven
21
Years of Service
User Offline
Joined: 2nd Oct 2002
Location: United States
Posted: 20th Mar 2006 23:16
Quote: "Back to the explosion problem, you could use raycasting. That way when you hit something in Newton, you could get the object hit, check if that object is static or dynamic, and react accordingly.
You would have to do at least 64 raycasts per explosion though "

Sorry man, but this is one of the worse ideas in the thread. It could easily miss small objects.

Anyway, I eventually went about it by just looping through all the objects in the game. Since I only need to do it once per grenade explosion there is absolutely no drop in frame rate at all. I check the distance to the object (using SQRT, anyone got a vector distance example?), then I cast a ray to the object to see if the level blocks the explosion force, then I blast it. Here's a beautiful screenshot of it in action:



And yes...that is a Mario 64 level...

RiiDii
19
Years of Service
User Offline
Joined: 20th Jan 2005
Location: Inatincan
Posted: 21st Mar 2006 10:51
Quote: "anyone got a vector distance example?"

Posted one 4 posts up.


Open MMORPG: It's your game!

Login to post a reply

Server time is: 2024-04-28 06:24:24
Your offset time is: 2024-04-28 06:24:24