Skip to main content
added 58 characters in body
Source Link
AJNeufeld
  • 34k
  • 5
  • 39
  • 101

You are wasting time computing the actual distance. Instead of getDist(), create a getDistSquared() function, and compare against the square of the vision distance.

creatureViewDistSquared = creatureViewDist * creatureViewDist
...

    if getDistSquared(creature.pos, otherC.pos) < creatureViewDistSquared:
        ...

But first, do the partitioning as suggested by maxb.


If you maintain a heading vector for each creature (dx,dy), you could “dot”dot that with a displacement vector to the observed creature. If the dot product is negative, the observed creature is more than 90° away from the heading/viewing direction. This will, on average, remove more than half of the creatures.

If the heading vector is normalized, the dot product would also need to be less than or equal to the viewing distance.

This will give you a fast filter, using only two multiples, two subtractions, and an addition:

dot_product = c.nx * (otherC.x - c.x)  +  c.ny * (otherC.y - c.y)
if dot_product >= 0  and  dot_product <= creatureViewDistance:
    ....

It occurs to me, you should also do the trivial reject first.

dx = otherC.x - c.x
dy = otherC.y - c.y
if abs(dx) > creatureViewDistance  or  abs(dy) > creatureViewDistance:
    continue

if dx*dx + dy*dy > creatureViewDistSquared:
    continue

dot_product = c.nx * dx  +  c.ny * dy
if dot_product >= 0  and  dot_product <= creatureViewDistance:
    ....

At this point, you can do the angle calculation, to ensure the creature is in the 60° limit

You are wasting time computing the actual distance. Instead of getDist(), create a getDistSquared() function, and compare against the square of the vision distance.

creatureViewDistSquared = creatureViewDist * creatureViewDist
...

    if getDistSquared(creature.pos, otherC.pos) < creatureViewDistSquared:
        ...

But first, do the partitioning as suggested by maxb.


If you maintain a heading vector for each creature (dx,dy), you could “dot” that with a displacement vector to the observed creature. If the dot product is negative, the observed creature is more than 90° away from the heading/viewing direction. This will, on average, remove more than half of the creatures.

If the heading vector is normalized, the dot product would also need to be less than or equal to the viewing distance.

This will give you a fast filter, using only two multiples, two subtractions, and an addition:

dot_product = c.nx * (otherC.x - c.x)  +  c.ny * (otherC.y - c.y)
if dot_product >= 0  and  dot_product <= creatureViewDistance:
    ....

It occurs to me, you should also do the trivial reject first.

dx = otherC.x - c.x
dy = otherC.y - c.y
if abs(dx) > creatureViewDistance  or  abs(dy) > creatureViewDistance:
    continue

if dx*dx + dy*dy > creatureViewDistSquared:
    continue

dot_product = c.nx * dx  +  c.ny * dy
if dot_product >= 0  and  dot_product <= creatureViewDistance:
    ....

At this point, you can do the angle calculation, to ensure the creature is in the 60° limit

You are wasting time computing the actual distance. Instead of getDist(), create a getDistSquared() function, and compare against the square of the vision distance.

creatureViewDistSquared = creatureViewDist * creatureViewDist
...

    if getDistSquared(creature.pos, otherC.pos) < creatureViewDistSquared:
        ...

But first, do the partitioning as suggested by maxb.


If you maintain a heading vector for each creature (dx,dy), you could dot that with a displacement vector to the observed creature. If the dot product is negative, the observed creature is more than 90° away from the heading/viewing direction. This will, on average, remove more than half of the creatures.

If the heading vector is normalized, the dot product would also need to be less than or equal to the viewing distance.

This will give you a fast filter, using only two multiples, two subtractions, and an addition:

dot_product = c.nx * (otherC.x - c.x)  +  c.ny * (otherC.y - c.y)
if dot_product >= 0  and  dot_product <= creatureViewDistance:
    ....

It occurs to me, you should also do the trivial reject first.

dx = otherC.x - c.x
dy = otherC.y - c.y
if abs(dx) > creatureViewDistance  or  abs(dy) > creatureViewDistance:
    continue

if dx*dx + dy*dy > creatureViewDistSquared:
    continue

dot_product = c.nx * dx  +  c.ny * dy
if dot_product >= 0  and  dot_product <= creatureViewDistance:
    ....

At this point, you can do the angle calculation, to ensure the creature is in the 60° limit

added 1192 characters in body
Source Link
AJNeufeld
  • 34k
  • 5
  • 39
  • 101

You are wasting time computing the actual distance. Instead of getDist(), create a getDistSquared() function, and compare against the square of the vision distance.

creatureViewDistSquared = creatureViewDist * creatureViewDist
...

    if getDistSquared(creature.pos, otherC.pos) < creatureViewDistSquared:
        ...

But first, do the partitioning as suggested by maxb.


If you maintain a heading vector for each creature (dx,dy), you could “dot” that with a displacement vector to the observed creature. If the dot product is negative, the observed creature is more than 90° away from the heading/viewing direction. This will, on average, remove more than half of the creatures.

If the heading vector is normalized, the dot product would also need to be less than or equal to the viewing distance.

This will give you a fast filter, using only two multiples, two subtractions, and an addition:

dot_product = c.nx * (otherC.x - c.x)  +  c.ny * (otherC.y - c.y)
if dot_product >= 0  and  dot_product <= creatureViewDistance:
    ....

It occurs to me, you should also do the trivial reject first.

dx = otherC.x - c.x
dy = otherC.y - c.y
if abs(dx) > creatureViewDistance  or  abs(dy) > creatureViewDistance:
    continue

if dx*dx + dy*dy > creatureViewDistSquared:
    continue

dot_product = c.nx * dx  +  c.ny * dy
if dot_product >= 0  and  dot_product <= creatureViewDistance:
    ....

At this point, you can do the angle calculation, to ensure the creature is in the 60° limit

You are wasting time computing the actual distance. Instead of getDist(), create a getDistSquared() function, and compare against the square of the vision distance.

creatureViewDistSquared = creatureViewDist * creatureViewDist
...

    if getDistSquared(creature.pos, otherC.pos) < creatureViewDistSquared:
        ...

But first, do the partitioning as suggested by maxb.

You are wasting time computing the actual distance. Instead of getDist(), create a getDistSquared() function, and compare against the square of the vision distance.

creatureViewDistSquared = creatureViewDist * creatureViewDist
...

    if getDistSquared(creature.pos, otherC.pos) < creatureViewDistSquared:
        ...

But first, do the partitioning as suggested by maxb.


If you maintain a heading vector for each creature (dx,dy), you could “dot” that with a displacement vector to the observed creature. If the dot product is negative, the observed creature is more than 90° away from the heading/viewing direction. This will, on average, remove more than half of the creatures.

If the heading vector is normalized, the dot product would also need to be less than or equal to the viewing distance.

This will give you a fast filter, using only two multiples, two subtractions, and an addition:

dot_product = c.nx * (otherC.x - c.x)  +  c.ny * (otherC.y - c.y)
if dot_product >= 0  and  dot_product <= creatureViewDistance:
    ....

It occurs to me, you should also do the trivial reject first.

dx = otherC.x - c.x
dy = otherC.y - c.y
if abs(dx) > creatureViewDistance  or  abs(dy) > creatureViewDistance:
    continue

if dx*dx + dy*dy > creatureViewDistSquared:
    continue

dot_product = c.nx * dx  +  c.ny * dy
if dot_product >= 0  and  dot_product <= creatureViewDistance:
    ....

At this point, you can do the angle calculation, to ensure the creature is in the 60° limit

Source Link
AJNeufeld
  • 34k
  • 5
  • 39
  • 101

You are wasting time computing the actual distance. Instead of getDist(), create a getDistSquared() function, and compare against the square of the vision distance.

creatureViewDistSquared = creatureViewDist * creatureViewDist
...

    if getDistSquared(creature.pos, otherC.pos) < creatureViewDistSquared:
        ...

But first, do the partitioning as suggested by maxb.