Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (754)
Games in Android Showcase (229)
games submitted by our members
Games in WIP (842)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Types of spatial partitioning  (Read 1790 times)
0 Members and 1 Guest are viewing this topic.
Offline Opiop
« Posted 2013-08-09 16:11:15 »

I have a 2D tile based game with dynamic entities and am wondering how I should group the different types of entities I have. I want to use frustum culling to limit the number of draw calls, however I don't want to check every single tile every frame. The same goes for my dynamic entities. I've decided that a quadtree is probably best for the enemies and such since they move around so much, however I've heard quadtrees are inefficient on modern day CPUs. Obviously, quadtrees would not be used to group together static tiles either. So my question is; what should I use to group the two types of entities I have?
Offline SHC
« Reply #1 - Posted 2013-08-09 17:41:02 »

You can create a grid for all the static tiles. You can use any other method for dynamic entities depending on their count.

Offline Opiop
« Reply #2 - Posted 2013-08-09 18:10:04 »

What do you mean any other method? Like a quadtree?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Jeremy
« Reply #3 - Posted 2013-08-09 19:29:40 »

For a tile based game you really only need to worry about the X and Y coordinate (or X and Z if it's an isometric game) which simplifies the task a bit. I think a quad-tree would be over-kill for a tile-based game anyway.

The way I do it (and it might be over-simplifying things - but it is easy to refactor if it begins causing performance issues) is simply have a series of 'sectors.' Each sector would be about 20x20 (or 40x40) - really it can be any dimension - obviously you also have to consider that if you are on corners of a sector that is adjacent to three other sectors you are now looking at processing 4 times your sector dimensions - which isn't that bad because you can perform the extra culling quite cheaply to determine which tiles are worth rendering of those sectors.

Each layer contains these sectors that are stored in a List. For convenience (and speed) there is another inner private class that is a very simple primitive 2D vector (nothing compared to your main game's Math vector - i.e it doesn't implement dot product or really anything - all it implements is the x\y public members (you really don't even need getters\setters.) This vector class overrides the equals method so that you can use it as an index into your list of sectors. The idea is that it compares with these sectors to test if the coordinates of the vector fall within the sector - you can index through your list of sectors like this.

Finally, when objects\tiles are created or when they move, they note when they've switched tile ownership - the tile they own is their tile-coordinate (their world coordinates rounded to the nearest tile) - you might already have this implemented for tile picking\collision whatever if you do that on a per-tile level. When they've transferred ownership they inform the world and the world moves them to the appropriate sectors by looking up their coordinate in the arrays of sectors.

The idea is that your sectors are created on a demand basis. So you get an X\Y coordinate, you index through your list of sectors using that X\Y coordinate as an index, if you list doesn't contain a sector for that coordinate you create one that contains the point and add that point to the sector.

Then when it comes time to render (and you know the tile bounds you need to render) you simply just pick up the appropriate sectors contained within that area and iterate through each entity contained in them (first doing standard culling to assure you aren't wasting CPU time on a draw call)

JevaEngine, Latest Playthrough (This demo is networked with a centralized server model)
Offline SHC
« Reply #4 - Posted 2013-08-10 05:36:06 »

In the book "Developing Games in Java", David Brackeen, the author uses a tilemap for static tiles and uses brute-force for dynamic entities in that map. The game is a platform game said in Chapter 5 of the book.

If you had a lot of dynamic entities, you can use a grid or quadtree for them but keep using the tilemap for the static tiles.

Pages: [1]
  ignore  |  Print  

DesertCoockie (20 views)
2018-05-13 18:23:11

nelsongames (68 views)
2018-04-24 18:15:36

nelsongames (65 views)
2018-04-24 18:14:32

ivj94 (748 views)
2018-03-24 14:47:39

ivj94 (79 views)
2018-03-24 14:46:31

ivj94 (595 views)
2018-03-24 14:43:53

Solater (95 views)
2018-03-17 05:04:08

nelsongames (168 views)
2018-03-05 17:56:34

Gornova (378 views)
2018-03-02 22:15:33

buddyBro (1038 views)
2018-02-28 16:59:18
Java Gaming Resources
by philfrei
2017-12-05 19:38:37

Java Gaming Resources
by philfrei
2017-12-05 19:37:39

Java Gaming Resources
by philfrei
2017-12-05 19:36:10

Java Gaming Resources
by philfrei
2017-12-05 19:33:10

List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!