PureBasic Forums - English

Posted: **Thu Mar 24, 2011 10:00 pm**

Some follow up questions...

I need to know of the most efficient and simple way to move an Element from one LinkedList to another LinkedList.. i.e I don't want to have to waste cycles manually re-creating the item in one list, and then deleting it from the other (unless it just doesn't matter to performance).. I haven't gone back and looked at the help Docs yet, but I think I saw a command in there but wasn't sure if it only worked within a List, or between unstructued global Lists..

Scenario:
Player enters a room and sees an uber cool sword laying on the ground. The sword resides in a LinkedList which is specific to that Room's Structure (so each room has its own List for contents to be fed into). Player picks up the sword, now ownership is transferred to the Player, and he puts it in his backpack, so now ownership is transfered to the Player's backpack. The sword needs to be physically moved (in memory) from the LinkedList attached to the Room, to the LinkedList attached to the backpack; so if you /look at the room the sword is gone, but if you looked in the backpack it would show up there.

Some other things worth pointing out:
I haven't decided if there will be a LinkedList for the Player's Hands - the above scenario suggests this would be necesarry, because the first ownership is from the Room to one of the Player's Hands (you cannot pick something up unless you have a free hand, and I am not using shortcuts like "Take sword" = bypassing the hands and going straight to a container)..

The Unique ID for Objects, while stored in a field in an Object's Structure, should only be accessed as a last resort. The way I intend to use UIDs with LinkedLists is that when an object is generated for the first time and placed into such a list, the List Element holding the object is named after its UID. I am hoping this design would allow easily handling Objects and copying them between Lists, etc.. The UID is only stored as a backup, for when the player saves and quits, and then comes back (the world has to be re-populated).

Posted: **Thu Mar 24, 2011 10:36 pm**

Don't use two Lists for the swords.
Just change the "parent". It's a common technique.
Imagine you have an "image.jpg" in C:\myImages\ and you want to move it to C:\Users\Name\Pictures\.
Windows doesn't "copy" the file onto another party of the HDD and then deletes it, but rather changes the properties of the file.
That's why moving a truckload of file from one folder to another on the same HDD is almost instantly.

So you just have one List for all Objects. Whether they are in room1 or room789 or in the inventory or in a chest in room1.

It then goes something like this:
Player enters room 1

Code: Select all

ForEach objects()
    If objects()\parent = 1
        Print("You see a " + objects()\name )
    Endif
Next

Player: "take sword"

Code: Select all

 ForEach objects()
    If objects()\name = ParserPutput() ;If objects()\ID = ParserOutput() ??
        objects()\parent = #Players_Hand
        Print("You took " + objects()\name )
    Endif
Next

It's really fast.
This takes 30-40ms.
There are a million objects in 10000 rooms.
Note: This takes longer if you have less rooms.
But if you have 1.000.000 objects in only 50 rooms maybe your game is a little too complex

Code: Select all

DisableDebugger 

Structure bla
	name.s
	id.i
	parent.i
	blub.i
	whatever.s
EndStructure 

NewList objects.bla()

For a=1 To 1000000
	AddElement(objects())
	With objects()
		\id = a
		\name = Str(a)
		\parent = Random(9999)
		\blub = Random(999999)
		\whatever = Str(Random(9))+ Str(Random(9))+ Str(Random(9))+ Str(Random(9))+ Str(Random(9))+ Str(Random(9))+"..."
	EndWith
Next 

MessageRequester("Loading Done","Starting Timer")

timer_start = ElapsedMilliseconds()

ForEach objects()
	Select objects()\parent 
		Case 579
			string$ + objects()\name + ";  "
	EndSelect 
Next 

timer_end = ElapsedMilliseconds()

MessageRequester("Timer", Str(timer_end - timer_start))
MessageRequester("Result", string$)

Posted: **Fri Mar 25, 2011 1:27 am**

Interesting.. I had initially considered using a global list for such things (I do have /owner fields so the change is minimal) but I had figured it would be too slow to iterate over stuff like that.

I don't know how many Rooms and Items I will end up with, but I would estimate a few thousand rooms, and Items number in the thousands (if not more). I still am a little weary of the list growing too big and iteration becoming slow, once a game is potentially underway and dynamic items are being generated, but I guess its easy enough to test those sorts of things.

Posted: **Fri Mar 25, 2011 1:58 am**

IF you want to use a Bubble-Loader that loads stuff from the database the list can't grow too big. You can delete every object from the list when the parent/room is more than x rooms away.
But my guess is that the ID must be Integer in order to compare if quickly.
If you use "1x7794569546" as a string it probably takes much longer.

Also for the IDs I would use seperate lists for rooms(no, rather anything that can contain an object, like chests) and objects. So you don't need types.
I don't know why you need an ID-type for the player, since there's usually only one??
Or did you mean NPCs in general?
If NPCs can handle objects they would need to be in the "room"-list.
But if you only give them an object and they act on it rather than really holding on to it (like they have an inventory of themself), and they just "drop" items (meaning the object is produced rathen than changes "parent" from NPC to Player) than that won't be necessary and they can have their own list, which structure contains their whereabouts and how they act (idle as well as interaction).

As for generating the IDs, I would simply start with 1 and count up 1.
Again that's a common technique. Why bother with random?

Code: Select all

Procedure.i CreateUID() ;Creates a unique ID
	Static lastID.i
	lastID + 1
	ProcedureReturn lastID
EndProcedure 


For a=5 To 17 			;Random numbers to show that the loop-variable 
	Debug CreateUID()	;has nothing to do with the creationprocess of the UID
Next 					;You can call CreateUID() whenever you like

Debug "..."

For a=67 To 74			
	Debug CreateUID()
Next

So for rooms and objects you need 2 procedures or a flag:

Code: Select all

Enumeration
	#Flag_Room
	#Flag_Object
EndEnumeration 

Procedure.i CreateUID(flag) ;Creates a unique ID
	Static lastID_Room.i
	Static lastID_Object.i
	
	Select flag
		Case #Flag_Room
			lastID_Room + 1
			ProcedureReturn lastID_Room
		Case #Flag_Object
			lastID_Object + 1
			ProcedureReturn lastID_Object
	EndSelect 
	
	ProcedureReturn -1
EndProcedure 


For a=5 To 13 					;Random numbers to show that the loop-variable 
	Debug CreateUID(#Flag_Room)	;has nothing to do with the creationprocess of the UID
Next 							;You can call CreateUID() whenever you like

Debug "..."

For a=67 To 74			
	Debug CreateUID(#Flag_Object)
Next 

Debug "..."

For a=1 To 7					;Create further Room-IDs	
	Debug CreateUID(#Flag_Room)	
Next

Posted: **Fri Mar 25, 2011 4:45 pm**

I agree with a lot of your points.

I don't need string based ID's but it was more about me catering to myself as the programmer, and using an addressing system I personally understand. However if string compares are going to be a hit to performance vs Integers then it makes sense I would want to choose integers.

I'm giving the player a GUID for reasons of foresight; I haven't decided on it yet but I am thinking of implementing a party-based system.. Like your typical Console / Computer CRPG these days uses. Certain NPC's may also require GUID's as there may come a point where a specific quest requires you to "group" with them in order to complete. Merchants and other important NPC figures will require a GUID also, because I will be implementing a reputation system, and other things of that nature that need to be kept up to date.

As for Monsters in general, I think I can get away with holding their generated items in the Global List with the rest, as when they spawn, they will be spawned as unique entities, with their own Stats, Skills, and Inventory. The reasons I initially was designing class prototypes with their own internal inventory lists, etc was because I am a little OCD about compartmentalized organization but I think you have convinced me to knock this down to a handful of global Lists (I'll still have quite a few but it is what it is..)

I will likely keep RoomID's as Strings in the (1xXX) fasion as they will be stored in a Map unlike the rest of the data, so lookup should be near instantaneous since I will be passing the target RoomID to the movement commands. Plus I absolutely need it for organizational and cartography related purposes.

You've been really helpful, so I appreciate it

Posted: **Fri Mar 25, 2011 6:44 pm**

If you use a structured map, you can have both. The "NxABC..." as the map-key and the equivalent of this value as an integer that is used to compare with the "parent" of an object.

1.000 rooms, 1.000.000 objects. Takes under 50ms on my system

Code: Select all

DisableDebugger 

Macro MakeStringKey(__val__)
	"1x"+RSet( Str(__val__), 8, "0")
EndMacro 


Structure room_properties
	iID.i		; UID as an integer
	sID.s		; string key again just to be sure
	
	exit_1.i 	; or .s whatever you prefer. 
	exit_2.i	; It's really not important at this point, 
	exit_3.i	; since this is only a "pointer" 
	exit_4.i	; and isn't used in heavy comparisons while iterating
	;more data....
EndStructure 

Structure object_properties
	ID.i
	parent.i
EndStructure 



NewMap 	rooms	.room_properties	()
NewList 	objects	.object_properties	()




Procedure makeUID_for_rooms(Map myMap.room_properties())
	Static lastID.i
	lastID + 1
	
	Protected key.s = MakeStringKey( lastID )
	
	myMap(key)\iID = lastID
	myMap(key)\sID = key
	
	ProcedureReturn lastID
EndProcedure 


For a=0 To 999					;Create 1000 rooms
	makeUID_for_rooms( rooms() )
Next 

For a=1 To 1000000	;Create objects
	AddElement(objects())
	objects()\ID = a ;...Could've used a UniqueID-Function, but this works, too for testing. It's unique after all.
	objects()\parent = Random(999)
Next 

;select a random room
number = Random(999)
room.s = MakeStringKey( number )


MessageRequester("You're in Room: "+room, "You see the following objects: ")

timer_start = ElapsedMilliseconds()

ForEach objects()
	If objects()\parent = number
		string$ + Str(objects()\id)
	EndIf 
Next 

timer_end =  ElapsedMilliseconds()

MessageRequester("Time: "+Str(timer_end - timer_start), string$)

Posted: **Fri Mar 25, 2011 7:00 pm**

Tops out at 16ms on my rig (C2D @ 3Ghz)

What is your CPU / Speed? Would be good to know the difference between them so I can estimate performance on slower machines.

Good to know that addressing system will work though (or at least seems to).. In other languages like Python, at least, when I tried casting them as Ints I got weird ass memory conflicts, like it was interpreting the Int as a memory address and trying to read that section of memory... So every since then I had used Strings to play it safe.

Posted: **Fri Mar 25, 2011 7:08 pm**

I'm not using integers to adresse the map.
I just created a macro that makes "1x00000001" out of 1 and "1x00098765" out of 98765.

My CPU: AMD Athlon X2 Dual Code QL-66 2.20 GHz
I have a 450MHz Machine here. If it'll still start up, I can give you the results

EDIT: But whatever the speed. It'll always be faster than building/updating the GUI.
You notice how the MessageRequester that contains all the objects, pops up only after some time.
The time between pressing OK on the first Requester and the second one showing up is much greater than the time that is displayed in the title.

Posted: **Fri Mar 25, 2011 7:29 pm**

I dunno, it was practically instantaneous for me? I'd say... 500ms max from click to pop-up..

Although that does concern me when you consider I will eventually be running other stuff in the background.. AI calculations, Spawn Control, and probably some other various background tasks..

I see what you mean in that you didn't cast them as Integers.. I actually realized that after I posted, but looking at your Macro just confused me even more

Hmm.. What about using Doubles ? The example

Code: Select all

value.d = 123.5e-20
  Debug value   ; will give 0.000000000000000001235

Works nice and allows me to use the (.) and (-) as delimiters.. but I don't actually understand the system used.. However it seems to create a unique number.
If you think its a good replacement and would be faster than Strings, or the Hybrid method you posted, could you help me understand the format ? If I knew how numbers were addressed in this system, I could easily replace my (1xA5) grid addressing system.. the .Period could replace my (x) and then I could use the (-) to indicate Z level

I want to have Maps that correspond to ID's that make sense in 3D space, i.e These tunnels running underneath the Town cross Main Street and zig down to the Weapons shop and zag back to the Church.. So if (on paper, as grid coordinates like I design my maps):

Main Street is ground level, and at coordinate:
001.5a-05 : (Area1.Lattitude5LongitudeA-Zdepth5)

A room that is part of the tunnel, directly underneath:
001.5a-04 : (Area1.Lattitude5LongitudeA-Zdepth4)

(Z Scale is 0 - 10, 5 being dead center i.e ground level)

Or am I just grasping at straws at this point

Sorry if I'm being stupid, or come off as stubborn. This is all a new process to me and I like to understand why things will/won't work better than others, and like just experimenting in general..

Posted: **Fri Mar 25, 2011 8:42 pm**

Anything other than integer has to be transformed to compare.
That goes for .b as well as for .q and last but not least for strings ofcourse.
Comparing string s goes as follows.

If "abc" = "abx" ->

Code: Select all

If Asc("a") = Asc("a")
    If Asc("b") = Asc("b")
        If Asc("c") = Asc("x")
            result = 1 ;True
            Goto jump_here
        Else
            result = 0
            Goto jump_here
             ;False  <<- This is where we break (jump out of the block) 
            ;After 3 Char-to-Int transformations and 3 Int comparisons.
        Endif
    Else
        result = 0 ;False
       Goto jump_here
    Endif
Else
    result = 0 ;False
       Goto jump_here
Endif
:jump_here
Debug result

You don't need to do everything every time the mainloop loops.

Code: Select all

Repeat
	what_to_do + 1
	Select what_to_do
		Case 1
			SpawnControl()
		Case 2
			Whatever()
		Case 3
			Blabla()
		Case 4 To 99
			Delay(5) 	;We can allow for plenty of idle-time. 
						;All of the above functions will still be called several times per second
		Default 
			what_to_do = 0
	EndSelect
ForEver ;Until....

About my last code:

Each room has an UID. That UID is simply stored as string and integer at once.
Storing the string isn't even necessary, but I did so anyway. It could be useful in the future and doesn't slow the process down much.
So you can access the room by its string-key. Whatever format that is.
At the same time PB only needs to compare the integer when iterating through the list.

So now it's gonna be more complicated if you want to access the room by its XYZ coords.
You must be able to calculate the Integer ID from the string and the other way round.
If you would store the room name as key. You would need a lookup list that is as big as the room list. -> Takes at least two times the time.
So you need to give each one of the directions another part in the number.
Just like RGB.

Code: Select all

Debug $FF0000 ;Blue
Debug $0000FF ;Red

Red is the lowest, than green than blue.
The integer is created as follows: Dec(RedPart) + Dec(GreenPart)*255 + Dec(BluePart)*255*255
If you were to simply add the values, the colors wouldn't be unique anymore: 255+0+0 = 255 and 0+0+255 = 255, too.

So you can use Hex or whatever (you could use for example a system based on 36 (26 letters + 10 numbers) which would enable you to create 1296 (36*36) rooms in each direction (actually that's 647 in each direction and up and down, if 0,0,0 is the middle rather than the corner of the cube).
Your ID would be: ZZ00AA for example. X:1296, Y:0, Z:100
Or you could use XXXYYYZZZ in Hex. Then your cube would be 4096*4096*4096 ~68billions of unique rooms if you fill the cube totally.

Ofcourse you are free to choose any limiter you want. XXX;YYY;ZZZ or XXX-YYY-ZZZ etc...

I'll follow with a short example of a cube of rooms where you can identify each one by its coordinates.

Posted: **Fri Mar 25, 2011 9:13 pm**

Hi, I think I have a solution.. It is a little harder for me to read, but it casts all IDs as Integers to maintain maximum speed.

Here is an example Map I just did in Visio, Illustrating how the addressing works.

http://www.oldskoolgames.com/pics/example_map.png

Posted: **Fri Mar 25, 2011 9:31 pm**

You can use strings.
No need to use 00 as a delimiter, if you rather like "-".

In this example I'm using "."

It's a small example where I position the player in a room defined by its XYZ coords.
Then I can look, if the player is in a certain room, by adressing this room with a string-ID.

Code: Select all

; Map-Key: "X.Y.Z"

Structure room_prop
	iID.i
	sID.s
	x.i
	y.i
	z.i
	playerhere.i ;1 or 0
EndStructure 

Global NewMap rooms.room_prop()

Procedure CreateRoom(x.i, y.i, z.i)
	Protected key.s = Str(x) + "." + Str(y) + "." + Str(z)
	Protected iID = x + 9*y + 81*z
	
	With rooms(key)
		\iID = iID
		\sID = key
		\x = x
		\y = y
		\z = z
	EndWith 
	ProcedureReturn iID
EndProcedure 

Procedure iID2Coords(id)
	z = id/81
	y = (id-z*81)/9
	x = id-z*81-y*9
EndProcedure 

Procedure Coords2iID(x.i, y.i, z.i)
	ProcedureReturn x + y*9 + z*81	
EndProcedure 

Procedure PositionPlayer(x.i, y.i, z.i)
	Protected iID = Coords2iID(x.i, y.i, z.i)
	ForEach rooms()
		If rooms()\iID = iID
			rooms()\playerhere = #True		
		Else 
			rooms()\playerhere = #False 
		EndIf 
	Next 
	ProcedureReturn iID
EndProcedure 


;.........

For a=1 To 3						;Create a cube of 3x3x3 (=27) rooms.
	For b=1 To 3
		For c= 1 To 3
			CreateRoom(a,b,c)			 
		Next
	Next
Next 


player = PositionPlayer(2, 2, 2) ;Position player in the middle

Debug rooms("1.2.3")\playerhere
Debug rooms("2.2.2")\playerhere
Debug rooms("3.1.1")\playerhere
Debug "..."

player = PositionPlayer(1, 2, 3) ;Position player somewhere else

Debug rooms("1.2.3")\playerhere
Debug rooms("2.2.2")\playerhere
Debug rooms("3.1.1")\playerhere
Debug "..."

Since the variable "player" contains the UID of the room an it's an integer. I could iterate through a huge list for some comparisons which will be very fast because I only compare integers.
The direct access to a specific room is the only time when strings are used.
And that's all it takes.

Posted: **Fri Mar 25, 2011 9:44 pm**

TomS wrote:I have a 450MHz Machine here. If it'll still start up, I can give you the results

Ok. There's no screen cable for this machine and I don't wanne take mine right now.
But here's another result.
It's from my EEE PC 4g. It has a 1GHz single core running WinXP.
The result is between 80 and 100ms.
Still pretty good.

Posted: **Fri Mar 25, 2011 9:51 pm**

Well, I'll consider what you've said. Although I am now kind of keen on the Integer based ID format I just created.

You have sparked another question in me though, relating to my prototype for my Player Structure.
It is going to be a relatively big Structure all by itself, because of all the information about the player that needs to be kept..

One section deals with Equipment Slots, i.e Restricting the Player so they can only use one piece of Armor in the appropriate Slot; This is the same for Accessories (Rings, Necklaces/Amulets etc) as well as Storage Items like Backpacks, Cloaks, Pouches, Sacks, etc.

I like using Boolean comparisons where possible, but wasn't really sure how restricted it was.. So for the various Equip Slots that I have defined, I cast them as Integers and Intend to flip them like ON/OFF switches (1=ON / 0=OFF). Naturally I would perform a check on the slot in question when the player attempts to equip an item of the Type that goes in the slot.

I like the idea of using the #True / #False contents, so maybe I will switch to that.. But I have a hunch it is really the same thing behind the scenes.

My real question is the following: I am not sure how to check multiple slots of a given slot-type and properly give the player permission to equip the item if at least 1 slot is available for use (or deny if no slots are free)
Can this be done in a single IF test?

Posted: **Fri Mar 25, 2011 10:04 pm**

Yes. #True and #False are constants for 1 and 0.
And each and every #True is replaced by 1 by the compiler, like every constant.
Doesn't matter if you use 1 or #True. The compiler-output will be identical.

I'm not sure if I understoof your question, but you can ask as much as you want in a single comparison.
But in the end it's just the same, again.

The only difference between:
If a = 1 and b = 2

and
If a=2
If b = 2

is what you see in the IDE.
If you think one of those is better readable, then use it.
Or use both.
While a one-liner looks clean and nice when you compare 2 or 2 values, it looks quite ugly and intimidating when you compare 10+ values.

So did you mean this?

Code: Select all

If \slot1 = 0 Or \slot2 = 0 Or \slot3 = 0
    Debug "There's at least one slot free"
Else
    Debug "Sorry. There's no slot available"
Endif

PureBasic Forums - English

Text RPG Design Thread [1 new, on: Screenshot, working cmd]

Re: Text RPG Design.. (General thread for various questions)

Re: Text RPG Design Thread [2 new questions]

Re: Text RPG Design Thread [2 new questions]

Re: Text RPG Design Thread [2 new questions]

Re: Text RPG Design Thread [2 new questions]

Re: Text RPG Design Thread

Re: Text RPG Design Thread

Re: Text RPG Design Thread

Re: Text RPG Design Thread

Re: Text RPG Design Thread

Re: Text RPG Design Thread

Re: Text RPG Design Thread

Re: Text RPG Design Thread

Re: Text RPG Design Thread

Re: Text RPG Design Thread