• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

babaliaris

Members
  • Content count

    13
  • Joined

  • Last visited

Community Reputation

112 Neutral

About babaliaris

  • Rank
    Member

Personal Information

  • Interests
    |programmer|
  1. I was thinking to make a hash table which each bucket will point to a quadtree. So instead of having only one big quadtree, i can have multiple. I think this will be a lot faster than having a single tree. Red lines represents the spatial hash table while the blue ones quadtrees. and of course all this will be applied during scene loading. Is this going to be better than having a single quadtree?
  2. There you stepped from (2097152*2097152) = 4,398,046,511,104 to (16777216 * 2) = 33,554,432, and you didn't wonder where the remaining 4,398,012,956,672 went? As a first suggestion, use powers of 2 everywhere, and don't bother expanding them to decimal numbers, as it only confuses matters. You are correct in 2^11 being the first value > 1920), so the number of entries in 1 one direction is 2^32 / 2^11 = 2^21   ( 2^a / 2^b = 2^(a-b) ) The full table has 2 such dimensions, giving you 2^21 * 2^21 = 2^42 cells. (that's 2^12 * 2^30 cells = 4096 GB if a cell takes 1 byte.) If you want to squeeze that in 32MB (2^25 byte), you get 2^42 / 2^25 = 2^17 cells in each single byte, or for 8 byte memory-bucket you get 2^(17+3) = 2^20 cells in a memory-bucket.   To be honest, I am lost here. Perhaps instead of throwing numbers around, take a step back, and describe some properties of the objects in your world first, so we can give some guidance about good and bad solutions? Some properties that come to mind: - World-size (given, 2^32 in both x and y direction). - Total number of objects in the world - Accuracy of positioning (integer positions, or fractions)? - How are objects spread? (evenly, clustered, everything in [0,1), something else? ) Under the assumption that not all objects are equally relevant all the time (eg stuff on the screen or "nearby" may be more relevant, so maybe only keep those in the table?) - How large is the "relevant" part of the world? - How many objects of the above are such a part? - How are they spread? - How close to each other are they?   Unfortunately i can't answer these questions. All of this depends on the programmer. My game engine is not designed to work for a specified game but to give functionalities in order other programmers be able to create 2d games very easy. But one of the problems i think can be sovled. I know that my full world is a square with length 2^32, but of of course the game programmer won't use all of this space. So, after he creates the scene when the game runs i can calculate which of these objects has the less x coordinate the greater x coordinate the y less coordinate and the y greater coordinate or even better i can force the programmer to tell me exactly the borders of his world. And using this coordinates i can create another square with length = less x coordinate + greater x coordinate (and make sure its power of two) to surround his world. So now i can use the new length in order to restrict the space and create a hash table only for that space. But i also must make sure that on runtime, nothing can go farther of this square (all the objects inlcuding new spawn ones) because if an objects has (x,y) coordinates greater than this square it will cause the hash function to return out of range keys. How does this sounds?
  3.   Yes, your math is correct and setting  42949672.96 = cell_size will make your lookup function work. However given how large your cells are this seems pretty large. I'm not sure how big sprites will be in your game, but the article recommended that the space of a cell be roughly twice as large as an average moving object in your game. Maybe a better course of action would be to determine how big you want your cells and use that equation above to find out how many you will need. Of course if you go for more cells you will have a larger array in memory, so you'll need to determine where the sweet spot is for performance. Larger spacial array and less objects to process per cell or a smaller spacial array with more objects per cell.  Another cool idea for performance tweaks would be to make sure your cell count is a power of 2 (which would make your cell size a power of 2 since your total world size is too) that way instead of dividing you can just right shift the bits of your coordinate (i.e. if cell_size = 2^6 instead of doing (int) (y / cell_size) you could do (int) (y >> 6) which is computationally cheaper than division, although it is less obvious programatically what you're doing). You are right, if my cell size is 42949672.96, then the spatial table won't do anything to increase performance since all of my objects most likely will be placed into a single bucket (Because buckets will be too big). So lets say that my biggest object has a width of 1920 pixels and a height of 1080 (Full HD LOL  :P ).  Lets say that my cell size will be the largest value (1920). 1920 its not a power of two so lets make it. If i do log2(1920) = 10.90689059560852 and ceil this number i will get 11. So the closest power of two will be 2^11 = 2048. Now i can easily say 2^32 / 2048 = 2097152. So now i must create a table of 2097152x2097152  :o  :o   RIP MEMORY! Actually, if we say that each bucket holds up to two integer numbers (8 bytes) 2097152 * 8 = 16777216 and 16777216  * 2 = 33554432 bytes = 32 MB. I guess its not that much.
  4. Hello! I read this article https://www.gamedev.net/resources/_/technical/game-programming/spatial-hashing-r2697 about spatial hashing but i have a question. In my 2d engine, the world's borders are specified and its actually a square with length 2^32 . In the spatial hash article, i read that in order to place a point inside a bucket you can use this hash function: row = (int) (y / cell_size), column = (int) (x / cell_size) . So if i have a 2d array, the function above will give me the row and the column of the 2d array where i have to insert my point. Then i said to my self "And how do you initialize the dimension of the array and also make sure that the hash function won't give you a row or a column out of range of the array?" Then i thought about this: Say that i want to divide my space in 100 squares. I know that my world is actually a square with length 2^32, so how do i find the size of the cell? In order to solve this i started thinking with mathematics so i reached to this: 2^32 / cell_size = 100 <=> cell_size  = 2^32 / 100 <=> cell_size  = 42949672.96 So this tell's me that i need to create a 2d array with dimensions 100x100 and each bucket (cell) will be a square with the above cell_size. Am i right? And if we assume that the maximum dimension of my world is 2^32 (square) then the hash function will always give me a number between 0 and 100 both for row and column because the x and y coordinates of a point will always be between -2^16 and 2^16 Please correct me if i am wrong.
  5. Unity

    Guys, i want an other advice too (For the quadtree). My quadtree is working like this: Every node can have a maximum amount of sprite objects (let's say 10 for this example) which they are stored in a list. If the length of the list become more than the maximum amount, the node will split. Sprite objects which are not entirly fit inside a region, will be place on the parent node. Take this scene as an example. The red cross represents the space division, the blue rectangles moving objects and the black rects static objects.   The quadtree will look something like that: As you can see, 11,12,13 are in the parent node, because they could'nt entirly fit inside of the 4 regions.     There are only 3 objects that can move around the scene with labels 1,2 and 3 (Blue ones). So in order to check for collision i must do something like that: moving = [1,2,3] #Go though all moving objects. for mov in moving: #Get the root of node of the quadtree. root = quadtree.root #While the root node is not a leaf. while not root.isLeaf(): #Get currents node sprite list. sprites = root.get_sprites() #Check collision of the moving sprite with the current sprite list. for sprite in sprites: if mov != sprite and mov.getCollision(sprite): #Collision detected!!! #Move to the next child depending on the moving's sprite position. root = root.getChild(mov.position) In words, for every moving object i must start checking for collision from the root of the quadtree and finish in a leaf. Only and only then i will be sure that i checked all the possible objects which might collide with my moving sprite, am i right?   Please not that the algorithm above will miss a check, because the while not root.isLeaf() wont check for collision with the last node. This can be fixed easily so don't worry about it right now.   Is this efficient? Should i correct something? Please advice me :P
  6. Unity

    Anyway! With all of your help i think i've got the solution! Just tell me how to create the hash function of a spatial hashing and i'm good to go!!! I will report back to you with my new results!
  7. Unity

      Yes a little faster:   Code: import pygame from pygame.locals import * pygame.init() screen = pygame.display.set_mode((600,600)) running = True image = pygame.image.load("enemy.jpg") clock = pygame.time.Clock() while running: clock.tick() #Fill the screen with black. screen.fill((0,0,0)) #Keyboard events. for event in pygame.event.get(): if event.type == QUIT: running = False break #Loop. x,y = 0,0 for i in range(15000): #If the image is for sure out of the window, just skip. if x > 700 or x < -100 and y > 700 or y < -100: pass #Else draw the image on the this position. else: screen.blit( image, (x,y) ) x += 100 y += 100 #Set for window title the fps. pygame.display.set_caption( str( int(clock.get_fps()) ) ) pygame.display.update() pygame.quit() But the problem is solved i guess. I just need to to delete this for loop and run a quadtree instead.
  8. Unity

      You are right. I aldready thought of it, but my problem was this: If i use a quadtree to render only the sprites which are "close" to the camera then the other sprites which i will skip, will also skip their logic (if those sprites have a script attached on them). So if an enemy is hunting the player but the player goes far enough from him (so the enemy will be placed somewhere else in the tree), then the sprite objects which are going to be choosed for rendering will not contain the enemy and also his script. So the enemy's logic will be paused until the player go back to the region where the enemy is inside the quadtree. This is why i had a for loop to go through all sprite objects into the scene and run the scipts.   But an hour ago i though of something really simple! Not all of the 15000 objects will have a script!!! Most of these objects will be something like a tree or a house or something else which do not require a logic. So why do i need to loop through all objects and run the scipt of each (if they have on)? Anyway i reached to this conclution: I will make a list containing all the sprite objects with scripts attached on them (Brained Objects).                                                                       I will also make a list containing moving objects (Moving Objects).                                                                                                                       Then i will create a spatial hash which its bucket will point to a quadtree. This mixed data structure will divide my whole space. I will consider that my whole world is a square with length 2^32 . Finally my main loop should look something like this (I'm using only quadtree in here without spatial hashing): def mainloop(self): #Get the sprite objects which are close to the camera. area = self.quadtree.get_area_for_render(self.camera.position) #Render those sprites. for sprite in area: sprite.render(self.screen) pass #Run scripts. for brained_sprite in self.Brained: brained_sprite.run_scripts() pass #Check collision. for moving_sprite in self.Moving: #Check the moving sprite if collides with all the sprites #which are close to him (using the quadtree). self.quadtree.checkCollision(moving_sprite) So i guess this will be better. The only think i dont know is how to create the spatial hash function. I already searched about spatial hashing and l learn that spatial hashing is dividing your space in squares with a length x and its square is actually a bucket of your array hash table. So the hash function must take as parameter a sprite object, and depending the x, y, width and height of this object (inculding the x value which is the length of its bucket) will return you a number between 0 and max_length_of_hash_table - 1 so you will know where excactly must place your sprite object. How do i make this mathematical function, i have no clue and i cant find something on the internet (Even if i'm good with maths)
  9. Unity

      You are right. I aldready thought of it, but my problem was this: If i use a quadtree to render only the sprites which are "close" to the camera then the other sprites which i will skip, will also skip their logic (if those sprites have a script attached on them). So if an enemy is hunting the player but the player goes far enough from him (so the enemy will be placed somewhere else in the tree), then the sprite objects which are going to be choosed for rendering will not contain the enemy and also his script. So the enemy's logic will be paused until the player go back to the region where the enemy is inside the quadtree. This is why i had a for loop to go through all sprite objects into the scene and run the scipts.   But an hour ago i though of something really simple! Not all of the 15000 objects will have a script!!! Most of these objects will be something like a tree or a house or something else which do not require a logic. So why do i need to loop through all objects and run the scipt of each (if they have on)? Anyway i reached to this conclution: I will make a list containing all the sprite objects with scripts attached on them (Brained Objects).                                                                       I will also make a list containing moving objects (Moving Objects).                                                                                                                       Then i will create a spatial hash which its bucket will point to a quadtree. This mixed data structure will divide my whole space. I will consider that my whole world is a square with length 2^32 . Finally my main loop should look something like this (I'm using only quadtree in here without spatial hashing): def mainloop(self): #Get the sprite objects which are close to the camera. area = self.quadtree.get_area_for_render(self.camera.position) #Render those sprites. for sprite in area: sprite.render(self.screen) pass #Run scripts. for brained_sprite in self.Brained: brained_sprite.run_scripts() pass #Check collision. for moving_sprite in self.Moving: #Check the moving sprite if collides with all the sprites #which are close to him (using the quadtree). self.quadtree.checkCollision(moving_sprite) So i guess this will be better.
  10. Unity

      The time is in seconds?
  11. Unity

    Yup, which means it'll never be as fast as using a sprite renderer that uses OpenGL or Direct3D. Why don't you profile your code using the script I provided? Then you'll know for sure if it's the sprite blitting that's slow or the onScreen check or something else.   I tried but it shows me so many other methods that python runs and its a mess. Isn't there any way to tell the profiler "ok, show me only my methods"?
  12. Unity

    OK! So i asked pygame developpers about the blitting method and they answered me: (1) PyGame is essentially CPU-bound rasterization. The fastest way to do this is with the Sprite module, or so I'm told.   (2) Using PyOpenGL instead of PyGame (for blitting, anyway), you instead use the GPU, which is deigned for doing just this. You have to know what you're doing, but it will probably be faster. In your case, most of your objects are off the screen, so you're probably CPU-bound anyway. If you really need more performance, and you really need to process every object every frame, you'll need to switch to a language with less overhead, like C++, or jitted like PyPy.
  13. Unity

    Since you count these off screen ones does that mean you don't cull them?     15000 * 2 =  30000 triangles = half a mesh buffer worth of triangles; so you don't batch your meshes. Learn batching, it is a process where you merge a lot of sprites into one as a way of saving performance.   If you did use batching you could get 64 000 triangles per mesh = 32 000 sprites per mesh = 32 000 * 300 (Mid range graphics card) = 96 000 00 static sprites. On a brand new graphics card you will get millions of static sprites.   You can start here: https://www.gamedev.net/resources/_/technical/opengl/opengl-batch-rendering-r3900 You could also search on the web, someone should have done it us So the basic idea is, instead of saying "Ok draw me 15000 rectangles", group pictures together to create one large image and draw this one on the screen? Like for example, 15000 / 50 = 300, so create 300 "big" images and draw these instead.   Also the method blit of pygame is not using graphics accelarator hardware.   But still, i don't think that this is the problem, because in this example ONLY six images are being rendered on the screen the rest 14996 are just skipped because of the if statement: def render(self, screen): if self.onScreen(screen) and self.image != None: screen.blit( self.image, self.pos )
  14. Unity

    Well, if you want to render as much sprites as possible then you could look into rendering using OpenGL or Direct3D. For fast collision you could try a Python port of Box2D or maybe somebody has made a different physics package for Python. But I'm wondering, you are going to use this engine to create a game with right? So wouldn't you rather focus on what that game needs?   Actually i'm trying to make something like Unity 3D but for 2D games with python :p Of course not too powerfull, just a start.
  15. Unity

    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.   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.