Jump to content


Photo

Grid Spatial Indexing


  • Please log in to reply
8 replies to this topic

#1 Damizean

Damizean

    GMC Member

  • New Member
  • 53 posts

Posted 09 October 2007 - 02:57 AM

Information
  • Name: Grid Spatial Indexing DLL
  • Author: Damizean
  • Version: 0.14
Description
Slowdown problems are always the worst enemy of the programmer (aside from creating tools to work with), that's why good methods for speeding up our application are needed.

Here I present a little DLL for Game Maker wich solves the problem of the slowdown on a scene full of static objects, such as solid collideables, animated scenery parts or the like: the Grid Spatial Indexing technique.

In a few words, it basically consists on dividing the scene in a grid-like structure, and creating an index of objects that are contained within each cell; for later managing of activation/deactivation.

My implementation is ridden through a DLL in order to take benefit of doing the calculations directly over the machine, instead of on the script layer. This is due the fact the checks done are too heavy for Game Maker to handle as fast as the DLL could do.

Pros and cons of using it
Pros:
+ Easy to use interface for the programmer. Create a Grid structure, register the objects and everything's ready to go.
+ Gives a tremendous boost on perfomance if used well: On a scene with 20.000 objects, with GM's default activation/deactivation system the perfomance I could get was of 200 fps. With the GSI technique, I got up to 2000 fps, being 900 the lowest peak. That's about 7x times faster. However, note that these results are the result of a simple room without collision interaction and such; depending on how much optimized your game is, these result may be variable.

Cons:
- It uses creation and destruction of instances, instead of activation/deactivation, so the instance's internal values aren't saved. In case you need to synchronice animation you could always use the current_time value, though.
- Due it's indexed nature, instances need to be static. This means that they shouldn't be able to move, because they won't be reindexed. However, you can use it for objects that need to move not much further of their initial spot, as long as you don't mind them resetting their positions once the player gets away.

Changelog
Version 0.1
  • First release
Version 0.11
  • Changed method for getting the size of an instance. Instead of relying on the registered object size, it relies on the instance's actual sprite size and offset.
  • Bugfixed some functions
Version 0.12
  • Small change on the activation/deactivation routine. Now, whenever an instance is created, a reference to the instance index, the grid structure and a deactivation flag is stored on the actual instance. This way, you can control when an object's destroyed due deactivation, or because the player catched it (variables __Grid_Reference, __Grid and __Grid_Deactivation respectively). This opens the system to more possibilities: you can have rings registered on the system, so when the player catches them, all you would need is to check if __Grid_Deactivation is true, and if so; call the scrGridInstance_SetExists to tell the GSI not to create the instance anymore.
Version 0.13
  • Now reference variables are created when the instance is acquired. This way, when destroying it after having indexed all instances won't make it crash (seems some people were having problems with GM passing the variable existance test for destroying, thus provoking a segfault).
  • I've also fixed a potential bug when managing the deactivation of the instances that have been manually destroyed. Now, the Exists flag is checked before trying to destroy the instance. Hopefully, this will be the last update of this kind <_<
  • Oh, yes. I've also added instance destruction on the example, that way you can see how to implement it on your games.
Version 0.14
  • Fixed some glitches in the DLL
  • Added instance reindexing. Basically, reindexes the instance on the grid, so the last position is saved and the grid is reorganizated: the GSI now allows to reposition instances. However, this shouldn't be extensively used, as reindexing the instance may be somewhat heavy in processing terms, so use it on strictly necessary.
License

===============================================
Grid Spatial Indexing library for Game Maker, v0.14, October 9th, 2007
  Copyright © 2007 Héctor Barreiro Cabrera
==================================================

  This software is provided 'as-is', without any express or implied
  warranty. In no event will the author be held liable for any damages
  arising from the use of this software.

  Permission is granted to anyone to use this software for any purpose,
  including commercial applications, and to alter it and redistribute it
  freely, subject to the following restrictions:

  1. The origin of this software must not be misrepresented; you must not
    claim that you wrote the original software. If you use this software
    in a product, an acknowledgment in the product documentation would be
    appreciated but is not required.
  2. Altered source versions must be plainly marked as such, and must not be
    misrepresented as being the original software.
  3. This notice may not be removed or altered from any source distribution.

                          -Héctor Barreiro Cabrera (elgigantedeyeso at gmail dot com)


Downloads
Download GSI v0.14

Edited by Damizean, 09 October 2007 - 03:00 AM.

  • 0

#2 Sindarin

Sindarin

    Indie Game Developer

  • New Member
  • 1644 posts
  • Version:GM:HTML5

Posted 09 October 2007 - 10:26 AM

The example confused me a bit. Can I position the instances exactly wherever I want?
Also, will this method be better than using tiles or deactivation?
  • 0

#3 dark_master4

dark_master4

    GMC Member

  • GMC Member
  • 1209 posts
  • Version:GM:Studio

Posted 09 October 2007 - 11:04 AM

Looking at the description, you should be able to place the instances wherever you want, you can even move them but hey will be reset when they leave the view.

Also, this method is faster than tiles and deactivation as they are completely deleted instead of being ignored when outside the view. Only the DLL (which runs compiled code) keeps track of the instances, which should be faster than deactivation. One thing only the maker can say though is wether tiles are faster or not.
  • 0

#4 Damizean

Damizean

    GMC Member

  • New Member
  • 53 posts

Posted 09 October 2007 - 11:13 AM

Exactly, dark_master4. However, using tiles should be faster for static scenery. This is meant for animated scenery, or static / objects that don't move too far away from their spawn position.

Edited by Damizean, 09 October 2007 - 12:24 PM.

  • 0

#5 gmjab

gmjab

    GMC Member

  • New Member
  • 784 posts

Posted 10 October 2007 - 09:37 PM

Good work. You should do a little test to see if your DLL is faster, lots of tiles can cause lag.
  • 0

#6 Sindarin

Sindarin

    Indie Game Developer

  • New Member
  • 1644 posts
  • Version:GM:HTML5

Posted 11 October 2007 - 12:40 PM

Another question: will it allow for multiple views?
  • 0

#7 Damizean

Damizean

    GMC Member

  • New Member
  • 53 posts

Posted 11 October 2007 - 03:36 PM

It does.
  • 0

#8 Maxinston

Maxinston

    Epic Phail

  • GMC Member
  • 1248 posts
  • Version:Unknown

Posted 22 March 2010 - 10:44 PM

Does someone still has the download? And is it as effective in GM8 as it were in GM6?
  • 0

#9 Overbound

Overbound

    GMC Member

  • GMC Member
  • 232 posts
  • Version:GM8

Posted 01 July 2010 - 11:32 PM

Just happened to run by this by accident. I'm hosting GSI still.
http://www.timetwist...g_015Update.rar
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users