- Name: Grid Spatial Indexing DLL
- Author: Damizean
- Version: 0.14
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
- 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
- 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.
- 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.
- 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.
===============================================
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.
