# Optimizing what can be seen by a creature

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

## 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 on other sites
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 viewedlet f = viewer's look at direction, normalisednormalise abif 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 frustrumlpn = normal to plane forming left hand edge of view frustrumab = vector from viewer to viewedif 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 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 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    nextnext

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 = 1for 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    nextnextwhile 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    nextwend

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 on other sites
Thanks, I'll give it a try.

##### 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 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 on other sites
Quote:
 Original post by NumsgilIs there a way to get to the angle of a vector defined in 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 vectorlet right = normalised right vector (perpendicular to at)let P = vector from observer to observed; project P into observer spaceP'x = P dot rightP'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 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 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:

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?

• 10
• 19
• 14
• 19
• 15