Before I start : Not that I think anyone actually takes anything here as a source of advice but... this obviously may be a completely stupid and incorrect way of doing things. All I will say is, it is a solution for a problem I have when programming with Monkey while at the same time being aware of how Xbox games created through XNA really do not like garbage (as you might be aware from my previous posts about Ninjah). I'd also like to state that I'm not writing this in a "hey, everyone should check this out" kind of way, more a "I've ready plenty of useful posts and it's only fair to contribute as well".
Ninjah is a really simple game, the amount of interactions between in game objects is minimal. To the point where I can list them...
- Ninjah against Level
- Ninjah against Coins
- Ninjah against Exit
- Rope against Level
- Bullets against Level
That's it. That's literally it. The code very specifically did these things. I went through each level block to see if Ninjah was touching them, did the same for each coins, did the same for the exit. Then I checked the rope (assuming it was out and not yet attached) against each level block and finally I checked the bullets against each level block (if bullet over wall, remove bullet).
Perling (now just a working title because I don't like it any more...), could potentially have 100 different object types and they could all interact with each other. So there could be 100 x 101 check combinations (the extra 1, is the level itself) and even if there are just 5 of each object type that's 100 x 101 x 4 checks (4 being 5 - 1 because you don't check an object against itself). That's 40400* checks for interaction per frame. (* There is almost certainly more to my some what crude calculation, but it's fine for an understanding of how many checks it'll do)
So, how do you check all of these objects? Hard coding it would lead to the below...
Ok, first check all the player objects against all the coin objects. Now check the player against all gem objects. Now check against the sparkly objects, and now the boxes, and now trees..... OK now check all the coin objects against the gem objects, and then the sparkly objects and then....
... nah. Click "Read More" to continue.
Assuming you remember each item type and also remember to change each series of item checks each time you add a new item type, the above is fine; but realistically, it's not manageable and (I speak for myself here) will almost certainly lead to bugs.
Monkey has plenty of list data structures, so why not just have a list of lists and go through them? This would be fine for going through all items and running a function on them (e.g. item.Update(), item.Render() ) but this doesn't really allow items to interact with each other. As far as I am aware, there's no easy way of saying to one object "you need to follow object 4 of that list", lists are just a series of items that know the previous item, and the next one, they don't know where they are in the list (unless they're the first or last item).
Arrays are great. They are just as useful as any list structure I've used but the key advantage is the fact you can easily say, "bring me item 4 in the list!" like so...
1 2 3 4 5
ArrayOfCoins:Coin For Local i:Int = 0 to 9 ArrayOfCoins[i] = New Coin() Next TheFourthCoin:Coin = ArrayOfCoins
(entry 0 is the first in an array, so entry 3 is actually the 4th one). So above I have 10 coins and I can easily make reference to whichever coin I want just by using the relative ID number (between 0 and 9).
Arrays of arrays
Better know as a 2D array (though technically, it is actually an array of arrays).
1 2 3 4 5 6 7 8
ArrayOfArrayOfCoins:Coin For Local x:Int = 0 To 9 ArrayOfArrayOfCoins[x] = New Coin For Local y:Int = 0 To 9 ArrayOfArrayOfCoins[x][y] = New Coin() Next Next ACoin:Coin = ArrayOfCoins
So ACoin makes reference to the coin in the second row and the 8th column of the array. Again, I can easily make reference to this coin by storing the coordinates, 1 and 7. But really there's no point having a 2D array of coins unless you know very specifically how you want them separated (maybe one row per screen in a platform game). We need a generic type that all game items will extend.
Shared Properties and Extending
All game items share some key features that allow them to interact. A very basic example would be some sort of spacial information as listed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Class GameItem Field X:Int Field Y:Int Field Width:Int Field Height:Int Method Update:Void() End Method Render:Void() End End
So every item in the game will have at the very least a position (X,Y) and dimensions (Width,Height). This will allow us to check whether objects are overlapping (interacting with) each other.
From this point forward my examples will include 5 object types and 10 instances of each object. We define the extended classes and the 2D item array as follows...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Class Player Extends GameItem .. End Class Coin Extends GameItem .. End Class Gem Extends GameItem .. End Class SomeEnemy Extends GameItem .. End Class AnotherEnemy Extends GameItem .. End
1 2 3 4 5 6 7
Items:GameItem = New GameItem For Local x:Int = 0 To 4 Items[x] = New GameItem For Local y:Int = 0 To 9 Items[x][y] = New GameItem() Next Next
The above example of initialising the arrays is still pointless because it's just creating GameItem's, not specific items. We need to store instances of each game item in the relevant row. Because these items all extend GameItem's, they can be stored in the Items array, this is important.
Each object type can be an int (e.g. 0 = a Player item, 1 = a Coin item and so on), but remembering these can be difficult, especially when and if we deal with hundreds of item types. I tend to make a static class which hosts Consts which better describe what the values mean.
1 2 3 4 5 6 7 8 9 10
Class ItemType Const PLAYER:Int = 0 Const COIN:Int = 1 Const GEM:Int = 3 Const SOME_ENEMY:Int = 4 Const ANOTHER_ENEMY:Int = 5 Const TYPES:Int = 6 End
We can make reference to these numbers using their name ItemType.PLAYER. For ease of reference, I also store a value for TYPES, which stores how many different types of objects we have (this helps with iteration). Now we can initialise the 2d array properly.
Items:GameItem = New GameItem[ItemType.TYPES] For Local x:Int = 0 To ItemType.Types - 1 Items[x] = New GameItem For Local y:Int = 0 To 9 Select x Case ItemType.PLAYER Items[x][y] = New Player() Case ItemType.COIN Items[x][y] = New Coin() Case ItemType.GEM Items[x][y] = New Gem() Case ItemType.SOME_ENEMY Items[x][y] = New SomeEnemy() Case ItemType.ANOTHER_ENEMY Items[x][y] = New AnotherEnemy() End Next Next
So there we go, we have a 2D array that stores many different object types. We can quickly make reference to all of the shared properties (X,Y,Width,Height) very easily now, so the 4th coin would be Items[ItemType.COIN] and the first player would be Items[ItemType.PLAYER].
Below iterates through every game item printing the X value
1 2 3 4 5
For Local parentType:Int = 0 To ItemType.TYPES - 1 For Local parentId:Int = 0 To 9 Print Items[parentType][parentId].X Next Next
We can extend this to compare each object to every other object.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
For Local parentType:Int = 0 To ItemType.TYPES - 1 For Local parentId:Int = 0 To 9 For Local childType:Int = 0 To ItemType.TYPES - 1 For Local childId:Int = 0 To 9 If parentType <> childType Or parentId <> childId If ItemOverItem(Items[parentType][parentId],Items[childType][childId]) = True ' DO STUFF HERE ! End End Next Next Next Next
There we have it, we check each item against each other item. The line If parentType <> childType Or parentId <> childId prevents the object from checking itself against itself, if we don't do this, we could see some very strange results!
We have barely scratched the surface, but in part two, I will write about optimizing the amount of checks required.
Continue to part 2.