NewsForumsCodeLogsGallerySpecsSearch

How many levels are possible?

BlitzMax Forums/BlitzMax Programming/How many levels are possible?

PowerPC603(Posted 2004) [#1]
Hi,

I've completely converted my loading-routines from B3D into BMax.

This is how I do it now (in BMax):

I have one type-instance called "Universe", which is a TUniverse type.
Inside this TUniverse, I have an array ASectors, which holds all pointers to all TSector type-instances inside the universe.
Inside each TSector, there's an array AStations, which holds all pointers to all stations inside this sector.

So, to get the name of the 3rd station inside sector 2, I simply can do this:

Print Universe.ASectors[2].AStations[3].Name$


How "deep" can I go with this approach?

As there need to be some extra "levels" further, because each station can have it's own list of commodities that are for sale there.

So, for the name of the 5th commodity inside the same station, I would have to do this:

Print Universe.ASectors[2].AStations[3].ACommodities[5].Name$


If you want the entire code (and try it for yourself to see how it works):
http://users.pandora.be/vge/SG/SG.zip


taxlerendiosk(Posted 2004) [#2]
I doubt I'll convey this very legibly, but - there is no real "depth" to it, you're just bouncing around in memory. Going "deeper" each step is really no more complex than going to the next item in a linked list. (I think.)


FlameDuck(Posted 2004) [#3]
How "deep" can I go with this approach?
Until you run out of physical memory. Probably performance is going to take a serious hit after you hit about 1/8th of available memory, as second chance cache misses increase, and the OS starts swapping memory like mad.


Robert(Posted 2004) [#4]
There is no real limit to how far you can go with this.


PowerPC603(Posted 2004) [#5]
Thanks guys.

This approach is kinda similar to using TLists, but by using arrays, I can always pinpoint the correct type-instance directly, instead of having to loop through all instances inside a TList to find a specific instance, which of course could replace the array.

Doing it this way, seems to be the easiest way for me to keep my entire universe organised.

In B3D I used a 1D array for the sector-type instances, a 2D array for all stations and a 3D array for all commodities.

Now each sector has it's own array of stations, and each station has it's own array for commodities.

There's no need for moving stuff, because the entire structure of the universe is written inside a datafile (very much like Freelancer).

I think running out of physical memory won't be much of a problem, because I've got 512Mb on my system and the universe-datafile should not exceed 25Mb or so.
This includes keywords for the game to interpret, so it knows which data to store in which type-instance's field.

As far as I can think ahead, the commodity-level will be the "deepest" level (maybe one more), and I'm not seeing any trouble with the cache right now (everything runs perfectly).


Hotcakes(Posted 2004) [#6]
Well if Mikkel's 1/8th estimation is accurate, don't run your code on anything less than a 256meg machine ;]


PowerPC603(Posted 2004) [#7]
Now I've updated my code to include a FlushMem in each function that doesn't return anything (also at the end of each type's method).
Is this actually a good approach?

Would it be best to:
- only use FlushMem after loading the entire datafile,
- or use FlushMem after each object (type-instance) has been created, to flush local variables that were used inside methods and functions?

I've checked the MemAlloced before I did this (place FlushMem inside each method) and it used about 200Kb memory (after loading all data about the universe).
After using FlushMem once, it reduced to about 15Kb.

Now I'm loading even more (some extra commodities, for which I also wrote the code today, to load those parameters) into memory and uses only 9Kb after the last FlushMem.

It seems that if you use FlushMem regularly, the memory is cleaned up much more than using it only once, after doing all stuff in one go.


FlameDuck(Posted 2004) [#8]
It would be best to use Flushmem only once in your program. Typically either right before, or right after the Flip.


PowerPC603(Posted 2004) [#9]
I tried commenting all FlushMem commands in the entire code.

Only right before the MemAlloced()-value is printed (just before exiting the program), the FlushMem still exists.

The value increases to 12484 bytes instead of 9284 bytes (when all FlushMems are in place).

Here's the entire code, so you can see for yourself, that using multiple FlushMems clean up more than using it only once, after everything has been processed.
To do it, comment out all FlushMems in all files, except the last one in the main file (SpaceGame.bmx).

http://users.pandora.be/vge/SG/SG2.zip

I'm not using the Flip yet, because it's only the loading of the datafile that exists in the code.
There are no graphics yet, and no main loop.


FlameDuck(Posted 2004) [#10]
Here's to entire code, so you can for yourself, that using multiple FlushMems clean up more than using it only once, after everything has been processed.
It certainly shouldn't. Have you checked for cyclic references? I won't have time to check the code until the week-end.


PowerPC603(Posted 2004) [#11]
AFAIK, there are no cyclic references.

The methods do this (each type's structure in basically the same):
- scan for datablocks from the file
- analyse them with Select Case statements
- if a valid datablock has been found:
1) resize the appropriate array (increase size by 1)
2) create new type-instance at that last index (that was just created)
3) load line by line from the file and analyse it
4) store values inside newly created type-instance

- go back to the start of this list, until EOF is reached

There are no variables that hold a type-reference, only the indexes of the arrays.

This is why I find it strange myself why multiple FlushMem's clean up more than only one FlushMem at the end.


Dreamora(Posted 2004) [#12]
Perhaps resizing an array technically means create one with the new size and copy the old. This way with every resize a unreferenced copy would be left over which might end up in a "clean up hierarchy" for this array so I can't be cleaned with 1 call of flushmem. ( just an idea ... as C doesn't know of dynamic arrays and other implementations follow this way in the background as well )

Did you check the whole thing using a TList while extending and create a array from it at the end of scan and compare the result?


PowerPC603(Posted 2004) [#13]
No, I didn't do that.
In fact, I didn't use a single TList at all.
Everything is put directly inside the array.

Are you suggesting that I:
- 1) create all instances and add them to a TList
- 2) calculate the size of the TLists (count the types linked to this TList)
- 3) then resize all arrays all at once and then copy the pointers to the array (and eventually clear the Tlists)?

This would actually kill the approach to simply add a new station to a sector (or a new commodity to a station) later in the game.

This loading-routine is only executed at the start of the game (and makes it possible to simply add stuff later on), so it really doesn't matter if it takes a little longer to proces with all these FlushMems, because nothing (for now, later on there will be a splashscreen) is animated, so the player will not "see" any slowdowns.


Perhaps resizing an array technically means create one with the new size and copy the old.



From what I can tell from the docs, that happens to be the case.
So actually it would be best to clean up right after the resizing of the array (to erase the old, unreferenced one)?


Dreamora(Posted 2004) [#14]
no that wasn't what I mean't

There is a listtoarray function that simply returns an array with the content of your list.

You could simply use a list all the time as TList is indexed as well ( only if you use the OO part, not as a "flat function" ). It is not as fast as a static array but if your array is resized often then TList would be faster.

I can only suggest you that you check out the linkedlist.bmx to see the possibilities of TList :) You will be surprised


PowerPC603(Posted 2004) [#15]
I've got this working:

Type TUniverse
	Field SectorList:TList = CreateList()

	Method AddNewSector(NewName$)
		TempSector:TSector = New TSector
		TempSector.Name$ = NewName$
		ListAddLast SectorList, TempSector
	End Method
End Type

Type TSector
	Field Name$
End Type

Global Universe:TUniverse = New TUniverse

Universe.AddNewSector("Sector 1")
Universe.AddNewSector("Sector 2")
Universe.AddNewSector("Sector 3")
Universe.AddNewSector("Sector 4")

For TempSector:TSector = EachIn Universe.SectorList
	Print TempSector.Name$
Next


But I cannot get the indexing in a TList to work.
I tried:
Print Universe.SectorList.ValueAtIndex(2)
Print Universe.SectorList.ValueAtIndex(2).Name$


The first line gives an error that an object cannot be converted to a string, the second one cannot find the identifier Name$.

I tried looking at the code inside the linkedlists.bmx module-sourcecode, but couldn't find anything that indicated an index (except the ValueAtIndex).

And most source-code is still a bit confusing for me (as you can see).


Dreamora(Posted 2004) [#16]
print TSector( Universe.SectorList.ValueAtIndex(2) ).name

TList always returns an instance of type "Object" which is the general basetype. You need to cast it to the type that you want it to be.


FlameDuck(Posted 2004) [#17]
The first line gives an error that an object cannot be converted to a string
Print is a bit picky about what input it takes. Make an accessor method in your sector type
Method GetName:String()
  Return Name$
End Method
and invoke that instead of accessing the field directly, that should work (providing it's been cast properly, see below).

the second one cannot find the identifier Name$.
Yup. You need to make a downcast. ValueAtIndex likely returns an Object object, you need a TSector. Try (untested) 
Print TSector(Universe.SectorList.ValueAtIndex(2)).Name$



PowerPC603(Posted 2004) [#18]
Now I don't get an error, but it just prints an empty line, if I use the line from Dreamora.

The other one works (the one FlameDuck stated):

Print TSector(Universe.SectorList.ValueAtIndex(2)).Name$



But doing all stuff this way, isn't that basically the same approach as with using arrays?

This way, the program is using TLists as arrays, but with a few more conversions (from Object to TSector, for example).

I'm sorry if I offend you, but I cannot see the difference between using arrays and TLists.
All can I see, is that using TLists is a bit more difficult (for me anyways).

I know the basic principe of a TList (as explained in many tutorials and other sources for Blitz+ and B3D), but using them is a bit harder.

The speed is not an issue, as the arrays are only resized during the loading-sequence of the game.
After the game is loaded and the main-menu appears, nothing happens anymore to these arrays.
They remain the same in memory during the entire game.

Except for some missions perhaps, which could add a temporary commodity to a station for transportation by the player or such things.
This would take one more resize of 1 array, which doesn't pose much of a problem, I think.

But when I'm at that point, I'm sure that I could create just a temporary commodity that is standalone (isn't part of a station), and act on that.

Or to create an empty station, that's only used when doing missions, which require the player for destroying it (also like Freelancer).
You couldn't dock with it and you wouldn't be able to trade with it, it would just be a structure in space, and it's only purpose is to be destroyed by the player, who receives money for blowing it up (money is issued by the person who gives the mission to the player, of course).

Only then (when accepting a mission), a new station is added to the SectorArray (which will be resized to hold this new station's pointer).
Or it could as well be created as a stand-alone station, where it's pointer is only held within a temporary pointer (variable).


Dreamora(Posted 2004) [#19]
right, my code was wrong ... sorry
at least the explanation why it does not work was right ... :)