I'm using python for coding.

So i'm making a game engine which the main loop is something like that:

def mainLoop(self):
    '''This loop run's every frame per second.'''
     
    #Go through all sprite objects inside this scene.
    for sprite in self.sprites:
        
        #Update the sprite inside the quadtree.
        if sprite.position.changed():
            self.quadtree.update(sprite)
        
        #Render the sprite only if it is inside the screen resolution.
        if sprite.onScreen():
            sprite.render()

        
        #----------Get possible collision----------#

        possible_collisions = self.quadtree.get()

        for object in possible_collisions:
            sprite.getCollision(object)

        #----------Get possible collision----------#
        
        #Run the logic of this sprite object.
        if sprite.hasScript():
            sprite.runScript()

Firstly i thought that the quadtree (for reducing the collision checks) was the problem. But it wasn't that, my quadtree is working perfectly. So in order to find out what was causing latency for a big amount of sprite objects into the scene, i disabled the collision detection algorithm and run the engine again in order to see if the efficiency will be better. Then i found out that it was still very slow. Finally the problem was the for loop. Even that the game loop wasn't doing to much to waste time, because the for loop was too big the frames where being delayed anyway.

So i thought of a solution but it costs in game mechanics. I will devide my scene using a quadtree, and i will only work with sprites inside this area (depended where the camera position is). So i will only run the scripts of those sprites. This will make the engine a lot faster but objects outside the specified area will be disabled because their scripts won't run. For example if an enemy is hunting the player, but the player moves far enough so the enemy will be placed in a quadtree node where is outside of the current node, the enemy's script will be disabled and he will freeze. In the image below, you can see how my scene will be devided.

Please notice that the red rectangles are not devisions of the scene but the big red rect is. The 9 rectangles shows how many windows the quadtree node is (A window has the screen (game) resolution).

The collision checks will also occur only for the sprites inside this area.

So the main loop now will loop like this:

def mainLoop(self):

    area = self.quadtree.get()

    for sprite in area:

        #Update the sprite inside the quadtree.
        if sprite.position.changed():
            self.quadtree.update(sprite)

        #Render the sprite only if it is inside the screen resolution.
        if sprite.onScreen():
            sprite.render()

        #This is O(N^2) but i think will be ok because the area list will not be to big.
        for sp in area:
            if sp != sprite:
                sp.getCollision(sprite)

        #Run the logic of this sprite object.
        if sprite.hasScript():
            sprite.runScript()

There must be a better solutions for this problem, so i'm hearing suggestions.

Thank you for your time.

Just from curiosity, in modern game engines like unity 3d, an enemy who is at the other side of the map while the player is in the oposite side, will the enemy's logic run? Also assume that the scene is realy big!!!

Well, one thing you can improve within your stated architecture is that if A.getCollission(B) updates both A's and B's collision-state buffers, you only need to touch each pair once.

for( i=1; i < area.members; ++i )
  for( j=i-1; j >= 0; --j )
    area.members[i].testCollision( area.members[j] );

Presumably each sprite's 'script' logic then resolves any collisions discovered during that phase.

Well, one thing you can improve within your stated architecture is that if A.getCollission(B) updates both A's and B's collision-state buffers, you only need to touch each pair once.

for( i=1; i < area.members; ++i )
  for( j=i-1; j >= 0; --j )
    area.members[i].testCollision( area.members[j] );

Presumably each sprite's 'script' logic then resolves any collisions discovered during that phase.

Yes i understand that and already know this. Just assume that this works perfectly. My main problem is the devision.

When you loop through self.sprites are you looking at every sprite in the scene even the ones that don't move? If your bottleneck is the number of sprites, maybe just checking the ones that can move would reduce the iterations of your main loop if done the first way. This way every collision will still have a dynamic sprite attached to it since your static objects don't move.

In modern game engines like Unity you can mark non-moving objects as static, and also the scripts on objects always run regardless of proximity to the camera.

Yes, i look every sprite. So what you are saying, is to split game objects to two lists and make the loop work something like this:

def mainLoop(self):
    
    '''staticSprites + movingSprites = all sprites inside the scene.'''

    for sprite in self.staticSprites:

        #Run static sprite scripts.
        #Render static sprite.

        for moving in self.movingSprites:

            #Run scripts of moving sprites.
            #Render moving sprites.
            #check collision using the quadtree and the moving sprites.

please notice that inside the quadtree exists all the gameobjects (static and none static)
because the quadtree is a space division 

@samoan62

I understood everything you said, but just to be sure i want to show all of you step by step what i'm doing in order to discuss the efficiency of my algorithms.

First i will show you a game with the only functionality of rendering 15000 sprite objects.

Structure:

Sprite Class:

class Sprite:

    def __init__(self, image = None, pos = (0,0), tag = ""):
        '''Constructor.'''

        self.image = image #Image.
        self.pos   = pos   #Position.
        self.tag   = tag   #A tag name.

        #Width and height of the sprite.
        self.width = image.get_width()
        self.height= image.get_height()


    def render(self, screen):
        '''Is drawing this sprite's image to the screen.'''

        #Draw the image into the screen.
        if self.onScreen(screen) and self.image != None:
            screen.blit(self.image, self.pos)
            



    def onScreen(self, screen):
        '''Return's True if this sprite is inside the screen borders.'''

        #Get the size of the screen.
        screenWidth, screenHeight = screen.get_size()

        #Get coordinates of this sprite.
        x, y = self.pos

        #Do the calculation.
        if x + self.width > 0 and x < screenWidth:
            if y + self.height > 0 and y < screenHeight:
                return True

        return False

        

Scene Class:

class Scene:

    def __init__(self):
        '''Constructor.'''

        #Sprites list.
        self.sprites = []



    def addSprite(self, sprite):
        '''Add a new sprite to the scene.'''
        self.sprites.append(sprite)



    def render(self, screen):
        '''Render this scene.'''

        #Go through all sprites in this scene.
        for sprite in self.sprites:

            #Render the sprite object.
            sprite.render(screen)

Core Class:

import pygame

from pygame.locals import *

class Core:

    def __init__(self, width, height):
        '''Constructor.'''

        pygame.init()
        self.pygame = pygame
        self.screen = pygame.display.set_mode((width, height))

        self.running = True
        self.scene   = None




    def mainloop(self):
        '''Main loop of the game, runs every frame.'''

        #Pygame clock.
        clock = pygame.time.Clock()

        while self.running:

            #Fill the screen with black color.
            self.screen.fill((0,0,0))

            #Check keyboard and mouse input.
            for event in pygame.event.get():

                #Quit button pressed.
                if event.type == QUIT:
                    self.running = False
                    break


            #Render the screen.
            if self.scene != None:
                self.scene.render(self.screen)


            #Count time.
            clock.tick()

            #Display the fps to the window title.
            pygame.display.set_caption( str( int(clock.get_fps()) ) )

            #Update the screen.
            pygame.display.update()

        #Destroy the window.
        pygame.quit()

Main Program:

import pyworld

#Create a game core.
core = pyworld.Core(600,600)

#Create a scene and load it to the core.
core.scene = pyworld.Scene()

#Add 15000 sprites into the scene.
x,y = 0,0
for i in range(15000):
    
    core.scene.addSprite( pyworld.Sprite(core.pygame.image.load("enemy.jpg"),
                                         pos = (x,y),
                                         tag = "enemy"+str(i)
                                         )
                        )
    x += 100
    y += 100
    

#Run the game.
core.mainloop()

print("Game Terminated!")

How it looks like:

As you can see only six images are rendered to the screen (the other 14996 are off the screen).

The fps are between 50-60. My processor is: AMD FX(tm) - 6350 Six Core 3.90 GHz.

Is it efficient for this processor to run 15000 game objects without scipts and collision detection at 50 fps?

Also notice that i'm using https://www.pygame.org/docs/ref/surface.html#pygame.Surface.blit to draw images to a window. But i guess this is fast enough, i don't know it's implementation.

Well i think its not efficient! Grand theft auto 5 has extremly better graphics with a big open world city and its running faster that the game i just made!!! How is this possible!!!

So in order to find out what was causing latency for a big amount of sprite objects into the scene, i disabled the collision detection algorithm and run the engine again in order to see if the efficiency will be better. Then i found out that it was still very slow.

If you want a reliable way of finding out what code is slow then your best bet is to profile your game. Luckily Python comes with a profiler in its standard library.

Just make a new python file and copy this into it:

import cProfile
import pstats
import your_game_module

profile = cProfile.Profile()
profile.runcall(your_game_module.main)

with open("profile_results.txt", 'w') as resultsFile:
    stats = pstats.Stats(profile, stream=resultsFile)
    stats.sort_stats('time') #cumulative
    stats.print_stats()

Replace the your_game_module with your own and run it. Then you'll have a much better idea of how much time everything takes.

Is it efficient for this processor to run 15000 game objects without scipts and collision detection at 50 fps?

Do you need your game to have this many objects? Keep in mind that Python is not the fastest language in the world and although I think it's a great language for making indie games with you will not be creating the next GTA V with it.

No it does not, but i'm trying to make my engine be able to handle as many gameobjects per scene it can, without lagging. This is my objective.