I have fairly simple collision checking and handling Python code which is currently bottlenecking my performance quite a bit. I haven't done too much coding in python and I'm quite sure there's something that could be done better:
Assuming I read this profiler correctly, get_nearby_entities is the biggest culprit.
Collision handling
In collision handling I go through all (moving) entities and find nearby entities from the collision grid (default search range is 9 closest cells).
def handle_collision():
for first in entities:
# Pair all possible combinations, but only once per pair
grid.remove_entity(first)
# all entities are readded to the grid at the start of next update
for second in grid.get_nearby_entities(first):
# Check and handle collision
Grid implementation:
In get_nearby_entities() I return list consisting entities from all cells within search radius. There's propably more efficient way to do this using Python.
import math
class Cell(object):
def __init__(self):
self.entities = []
def add_entity(self, entity):
self.entities.append(entity)
def remove_entity(self, entity):
self.entities.remove(entity)
def clear(self):
del self.entities[:]
class CollisionGrid(object):
def __init__(self, width, height, cell_size):
self.width = width
self.height = height
self.cell_size = cell_size
self.cols = int(math.ceil((self.width / cell_size)))
self.rows = int(math.ceil((self.height / cell_size)))
self.cells = [Cell() for _ in range(self.rows*self.cols)]
def add_entity(self, entity):
self.get_cell(entity.position).add_entity(entity)
def remove_entity(self, entity):
self.get_cell(entity.position).remove_entity(entity)
def get_nearby_entities(self, entity, radius = None):
if(not radius):
radius = self.cell_size
entities = []
min_x = int((entity.position.x - radius) / self.cell_size)
min_y = int((entity.position.y - radius) / self.cell_size)
max_x = int(min_x + 2*radius/self.cell_size + 1)
max_y = int(min_y + 2*radius/self.cell_size + 1)
if (min_x < 0): min_x = 0
if (min_y < 0): min_y = 0
if (max_x >= self.cols): max_x = self.cols
if (max_y >= self.rows): max_y = self.rows
for y in range(min_y, max_y):
for x in range(min_x, max_x):
entities.extend(self.cells[self.cols*y + x].entities)
return entities
def get_cell(self, position):
return self.cells[int(position.x / self.cell_size) +
int(position.y / self.cell_size) * self.cols]
def clear(self):
for c in self.cells:
c.clear()
Picture of few entities in collision grid:
It is after 200 entities when simulation really starts to slow down:
Test main:
import sfml as sf
import math
from entity import Entity
from collision_grid import CollisionGrid
WIDTH = 1280
HEIGHT = 720
Entity.SIZE = 50
settings = sf.window.ContextSettings()
settings.antialiasing_level = 8
window = sf.RenderWindow(sf.VideoMode(WIDTH, HEIGHT), "Collision Test",
sf.Style.DEFAULT, settings)
entities = []
grid = CollisionGrid(WIDTH, HEIGHT, Entity.SIZE)
time_per_frame = sf.seconds(1/60)
class Statistics(object):
def __init__(self, font):
self.text = sf.Text()
self.update_time = sf.seconds(0)
self.num_frames = 0
self.text.font = font
self.text.position = (5, 5)
self.text.character_size = 18
self.num_entities = 0
self.collision_checks = 0
def update(self, dt):
statistics.num_frames += 1
statistics.update_time += dt
if (self.update_time >= sf.seconds(0.1)):
fps = int(self.num_frames / self.update_time.seconds)
tps = int(self.update_time.microseconds / self.num_frames)
text = "FPS: " + str(fps) + "\n"
text += "update: " + str(tps) + " us\n"
text += "entities: " + str(self.num_entities) + "\n"
text += "collision checks: " + str(self.collision_checks) + "\n"
self.text.string = text
self.update_time -= sf.seconds(0.1)
self.num_frames = 0
def draw(self, target):
target.draw(self.text)
font = sf.Font.from_file("Media/Fonts/Sansation.ttf")
statistics = Statistics(font)
def process_events():
for event in window.events:
if type(event) is sf.CloseEvent:
window.close()
elif type(event) is sf.KeyEvent and event.code is sf.Keyboard.ESCAPE:
window.close()
elif type(event) is sf.MouseButtonEvent and event.pressed:
entities.append(Entity(event.position, sf.Color.GREEN))
def update(dt):
for e in entities:
e.update(dt)
if (e.position.x < 0):
e.position.x += WIDTH
elif (e.position.x > WIDTH):
e.position.x -= WIDTH
if (e.position.y < 0):
e.position.y += HEIGHT
elif (e.position.y > HEIGHT):
e.position.y -= HEIGHT
def render():
window.clear()
for e in entities:
e.draw(window)
grid.draw(window)
statistics.draw(window)
window.display()
def update_grid():
for e in entities:
grid.add_entity(e)
def handle_collision():
statistics.num_entities = len(entities)
statistics.collision_checks = 0
for f in entities:
# Pair all possible combinations, but only once per pair
grid.remove_entity(f)
for s in grid.get_nearby_entities(f):
statistics.collision_checks += 1
d = s.position - f.position
if (not (d.x or d.y)):
d.x += 0.1
distance = math.sqrt(d.x**2 + d.y**2)
radii = f.shape.radius + s.shape.radius
if (distance < radii):
offset = d * (radii/distance - 1)
f.velocity -= offset/2
s.velocity += offset/2
if __name__ == "__main__":
clock = sf.Clock()
time_since_last_update = sf.seconds(0)
for i in range(200):
entities.append(Entity(sf.Vector2(75+int(i%23)*50, 75+int(i/23)*50), sf.Color.GREEN))
while window.is_open:
dt = clock.restart()
time_since_last_update += dt
while time_since_last_update > time_per_frame:
time_since_last_update -= time_per_frame
process_events()
update_grid()
handle_collision()
grid.clear()
update(time_per_frame)
statistics.update(dt)
render()
Entity
import sfml as sf
import utility
class Entity(object):
SIZE = 50
def __init__(self, position, color):
self.shape = sf.CircleShape()
self.shape.radius = Entity.SIZE/2
self.shape.fill_color = sf.Color.TRANSPARENT
self.shape.outline_color = color
self.shape.outline_thickness = 1
self.position = position
self.velocity = sf.Vector2()
self.line = sf.VertexArray(sf.PrimitiveType.LINES, 2)
def update(self, dt):
self.position += self.velocity * dt.seconds
speed = utility.length(self.velocity)
if (speed > 0.1):
self.velocity -= utility.unit_vector(self.velocity) * 0.1
else:
self.velocity.x = 0
self.velocity.y = 0
def draw(self, target):
self.shape.position = self.position - self.shape.radius
self.line[0].position = self.position
self.line[1].position = self.position + self.velocity
target.draw(self.shape)
target.draw(self.line)
Utility methods used by Entity
def length(vector):
return math.sqrt(vector.x * vector.x + vector.y * vector.y)
def unit_vector(vector):
return vector / length(vector)
Entityclass. \$\endgroup\$