• Advertisement
Sign in to follow this  

Optimizing what can be seen by a creature

This topic is 4738 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a program I'm optimizing. I have a bunch of spheres that are little creatures. Each creature has a 90 degree vision range. If there's another creature in its viewing range, and it hasn't seen a nearer creature already that cycle, it writes a number to a memory location the creature can access. Like this (but simplified, in reality the bot has 9 memory locations instead of 3). The creature is looking towards the blue arrow. Creature 1 will write numbers to eye cells 1 and 2, but not 3. The spheres are not necessarily uniform in size, but most are. Currently the program does these steps: 1. Caclulate distance between two spheres using their centers. 2. Calculate angle between two spheres. (uses atn((1.y - 2.y)/(1.x-2.x))) 3. If angle between spheres is within 45 degrees of creature 1's blue arrow then: 5. Find all eye cells that the creature in the distance is visible from. 6. If distance between the spheres is less than what is currently written to an eye cell, overwrite that eye cell. I've already optimized finding the distance between two cells. The only optimization left is to just use the square instead of the square root of the distance (which might not be a bad idea, I'm still evaluating). The problem is it's executed every cycle, becoming increasingly expensive as the number of creatures increases. At around 1000 creatures it hits a stand still. (like 2 cycles a second). I'd really like to double or even triple this, or even more! If you need to see the source code, I can post it. It's visual basic, so it shouldn't be too hard to understand (stop scoffing, it wasn't my idea!). Any ideas on how to combine steps or make steps faster would be awesome.

Share this post


Link to post
Share on other sites
Advertisement
The first obvious problem is the atan (dy/dx) as this involves division, which is slow, and a transendental function - which make division look speedy by comparison.

There's two ways to determine if one object is within the view angle of a second object that don't require angles. The first is:

let ab = vector from viewer to viewed
let f = viewer's look at direction, normalised
normalise ab
if ab dot f < cos 45O then object in view angle

which is OK apart from the normalisation of vector ab. Or there's the following:

rpn = normal to plane forming right hand edge of view frustrum
lpn = normal to plane forming left hand edge of view frustrum
ab = vector from viewer to viewed
if ab dot rpn >= 0 && ab dot lpn >= 0 then object in view angle

which is much better performance wise - the only operations are addition and multiplication.

The next problem is handling lots of objects. You need to look into some form of space division. The simplest would be a 2d array of lists of objects, each element of the array contains a list of objects in the same area such that:

array_index = ((object_x - origin_x) / cell_size) + ((object_y - origin_y) / cell_size) * array_width

Then, when an object moves, first remove it from the array cell it's currently in, move the object and add it to list for its new location. To search, start with the cell the object is in and the eight adjacent cells. If no object found then extend the search by one square and repeat.

Skizz

Share this post


Link to post
Share on other sites
Thanks, I'll give the second technique you showed a try, looks like it'll definately help. It actually looks simpler than what's going on right now.

Another programmer is working on adding a grid of squares roughly the size of the creatures to hold things like food sources etc. in the environment. I can adapt these to each hold a list of creatures that occupy the cell fairly easily.

If I were to use this system, how would you recommend using it to speed up the program? Other than what you've listed above of course (actually, could you explain that in a paragraph too?). Are there any other ways?

I have a few ideas, but I tend to reinvent alot of wheels. Duplication of effort is not my idea of a fun time.

Share this post


Link to post
Share on other sites
Well, what you're probably doing right now is something along the lines of:

for each object1 in world
for each object2 in world
if object1 can see object2 and object2 is the closest
do something with object2
endif
next
next

Using a 2D array, assume the world is bounded thus:

(0,0) <= object pos < (max_x, max_y);

and that the 2D array is defined as:

map [map_size_x][map_size_y];

then, each element of the array is (max_x / map_size_x, max_y / map_size_y) in size.

Given a position P, the index into the map is:

map [Px * map_size_x / max_x][Py * map_size_y / max_y]

So, to search the map do the following:

org_x = Px * map_size_x / max_x;
org_y = Py * map_size_y / max_y;
size = 1

for y = org_y - size to org_y + size
for x = org_x - size to org_x + size
for each object in map [x][y]
do object test
next
next
next

while no object found
size = size + 1
for y = org_y - size to org_y + size
for each object in map [org_x - size][y]
do object test
next
for each object in map [org_x + size][y]
do object test
next
next
for x = org_x - size +1 to org_x + size - 1
for each object in map [x][org_y - size]
do object test
next
for each object in map [x][org_y + size]
do object test
next
next
wend

The food thing can also be added to the map array as a separate list - it will take up less memory than what you've suggested. You'd want the cell size to be about 4 times the size of a creature.

The downside to this algorithm is that the cells are fixed size. If you get a lot of creatures grouped together, the search time will increase. To get around this, you can look into things like quad trees which can dynamincally change the size of the cells.

Hope that helps.

Skizz

Share this post


Link to post
Share on other sites
Is there a way to get to the angle of a vector defined in <x,y> form without using acos, asin, or atan?

Share this post


Link to post
Share on other sites
there is always a lookup table with interpolation. alternatively, if you are just partitioning something (i.e. -90 to -45, -45 to 0, 0 to 45, 45 to 90) you do not need an actual angle, as you could just leave the value as a cosine or sine or whatever.

if it is for small angles you can just a simple polynomial (taylor series expansion around your midpoint)

Share this post


Link to post
Share on other sites
Quote:
Original post by Numsgil
Is there a way to get to the angle of a vector defined in <x,y> form without using acos, asin, or atan?

Perhaps you should ask yourself "Do I need to know the value of the angle?"
If it's for working out which sector the object is in (the 'Eyecell' in your diagram) then this can be worked out without knowing the angle:

let at = normalised forward vector
let right = normalised right vector (perpendicular to at)
let P = vector from observer to observed

; project P into observer space
P'x = P dot right
P'y = P dot at

; you now have this:
; y| P'
; | /
; | /
; |/____ x
; now determine point on y=1 where OP intersects:

let n = P'x / P'y

; now compare n against values for tan theta where theta is the angle defining the eyecell.
; these values are constant so they can be precomputed and stored in an array


Skizz

Share this post


Link to post
Share on other sites
Hm.

I'd say as your number of creatures increase, the number of "empty" eyecells goes down to zero.
If this happens it would make sense to save the maximal distance of all creatures in all eyecells.

so if you have 3 eyecells at all (like in your example) with detected creatures at 100, 30 and 50; the maximum distance of a creature in your eyecells would be 100. now it wouldn't make sense to do any further calculation if you find out in your step 1 the distance of a creature is 101, as it never will be closer than any creature in your eyecell.

(you would still have to do all the work if you haven't found any creature in at least one eyecell)

sure this works only in an average case, if all creatures you have to view are in the same direction you will not benefit at all, but with MANY creatures you should get at least some speed boost.

Share this post


Link to post
Share on other sites
Small problem:

The P vector you gave is from the center of creature 1 to the center of creature two.

I'd like to have two vectors to get your system to work. P1 would be the vector to the right most visible edge of creature 2.

P2 would be the same but left most visible edge.

I've gotten this far:

P1 = P + RadiusRightAngle
P2 = P - RadiusRightAngle

where RadiusRightAngle is a vector of <x,y> and has these properties:

x/y = -P1y / P1x * y
x^2 + y^2 = creature's radius ^ 2

Then you have x = -P1y/P1x
creature's radius ^ 2 / (P1y^2/P1x^2 + 1) = y^2

y^2 can be calculated, then you get:

radius ^ 2 - y ^ 2 = x ^ 2

And then I'm stuck. I don't want to take the square root of any numbers.

Is there a better way?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I think that x/y = -P1y / P1x * y is wrong and should be x/y = -P1y / P1x.


Tricky problem this. Here's my solution though.

Let A be the centre of the observed creature which has a radius r. Let O be the centre of the observer which is (0,0). The B be a point on the circle of radius r with origin A such that OB is the left/right most point as viewed from O.

Since OB is tangential to the circle, OB dot AB = 0 since they are perpendicular.

This give us:

Bx(Bx - Ax) + By(By - Ay) = 0

=> -AxBx + Bx2 - AyBy + By2 = 0 [1]
=> Ax2 - 2AxBx + Bx2 + Ay2 - 2AyBy + By2 = Ax2 - AxBx + Ay2 - AyBy [2]

We also know that |AB| = r,

(Ax - Bx)2 + (Ay - By)2 = r2 [3]

Combining [2] and [3] yields:

Ax2 - AxBx + Ay2 - AyBy = r2

which will give you By in terms of Bx. Substitute By into equation [1] and you'll get a quadratic for Bx which will give you the two solutions for B.

So, you'll end up doing 3 square roots to find P1 and P2. I don't think you can get away without doing this as the problem has multiple solutions the square root gives you these multiple results (+ve and -ve roots).

Skizz

Share this post


Link to post
Share on other sites
Are you checking the distance, angle, and everything else all the time or are you doing it so if the distance isn't great enough then you check the angle.

like this (I just made up these variables I don't know what you use)

if (object.distance < visibledistance)
{
if (abs(object.angle - anglefromotherobject) < 45)
{
...and so on...
}
}

rather than

if (object.distance < visibledistance && abs(object.angle - anglefromotherobject) < 45 ... and so on)
{

}

You also might considering only checking so many creatures every frame.

Share this post


Link to post
Share on other sites
I'm doing nested ifs all the way.

First I check too see if I need to check creatures to the left or right.
THen I test partial distances (dx and dy)
Then I test actual distances
Then I test if it's in the viewing angle
THen I calculate which viewing angle it's in.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement