Any suggestions on the best way to set up a linked list?

New to FreeBASIC? Post your questions here.
olympic sleeper
Posts: 41
Joined: Jun 07, 2020 15:47

Any suggestions on the best way to set up a linked list?

Post by olympic sleeper »

Hi,

I am strugging to remember how to set up a linked list.

I have this structure:

Code: Select all

type obj
	name as string
	long_name as string
	additional_desc as string
	location as integer
	weight as integer
	size as integer
	description as string
	hold_size as integer
	surface_size as integer		'if you can put something on it how large the surface is
	holding as integer
	surface as integer			'total size of things on surface
	closed as ubyte			'0 is closable,1 is closed,2 is lockable, 3 is locked
	status as ubyte			'bit value bit 0 is in,1 is on (mutually exclusive), 2 is hidden, 4 is wearable, 5 is being worn,6 is carried
	cloth_type as integer		'if its clothing relates to the tyep as follows
							'1 is hat, 2 is body underwear, 3 is body mid layer (shirts), 4 is body upper (jumper), 5 is body outer (coat)
							'6 is legs under, 7 is legs mid (trousers), 8 is legs outer (water proofs), 9 is socks, 10 is shoes
	holds_list as string		'the numbers of the contained objects in the form <object><object>....<last object>
	surface_list as string		'the numbers of the objects on its surface in the form <object><object>....<last object>
	location as integer			'objects location (points to room or container)
	next_object_ptr as integer	'pointer to next object in the list
	objects_in_ptr as integer	'pointer to any objects inside this one
	objects_on_ptr as integer	'pointer to any objects on this one
	objects_under_ptr as integer	'pointer to any objects under this one
end type
the objects are stored in a simple 1d array (objects(400) as obj) I have a set of data lines which store the name,long name etc as well as the location

I read the object's location etc for each one in a loop so each object will now have its location, but no links to any other objects in the same place and need some way of linking the objects together so that I have something like:

room ->object->object->object(n)

The only way I can figure it out is to have 2 loops like this in pseudocode

Code: Select all


loop a for each object_a
loop b for each object_b

if object_a.location=object_b.location then
	if object_a.next_object_ptr =0 then 
		object_a.next_object_ptr=object_b

end loop b
end loop a

It does not seem very efficent and I'm not sure I have the assignment for the link correct in anycase. I am also not sure how to link the associated room structure into this, I suspect I will need another loop , going through rooms?

Here's that structure

Code: Select all

type rooms
	long_desc as string
	short_desc as string
	directions as string
	invalid as string
	visited as integer
	object_ptr as integer
end type
Anyone know of a better way to set up a linked list?

Thanks in advance.
Lost Zergling
Posts: 534
Joined: Dec 02, 2011 22:51
Location: France

Re: Any suggestions on the best way to set up a linked list?

Post by Lost Zergling »

I m not sure this can be of some help, anyway.. Consider using a linked list as an "entry point" rather than as a "service" called by an object instance. So far, I would use my lzle library to store variable len strings and associate to keys, and then to go from string to array to instanciate related objects on requirement rather than trying to link and manage instanciated object with a linked list. This would just be a solution trying to do it, but the relevance would depend on the structure of datas and algos. As you need to work on instanciated objects simultaneously this solution might not be adapted whereas on working on a subset out from large dataset the list entry point approach might be usefull to consider.
Anyway, I shall be interested by any remarks on this topic.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Any suggestions on the best way to set up a linked list?

Post by paul doe »

olympic sleeper wrote:...
I read the object's location etc for each one in a loop so each object will now have its location, but no links to any other objects in the same place and need some way of linking the objects together so that I have something like:
...
Laying out the linked list as an array, and using a handler instead of a pointer is a good idea; linking objects against each other is not. As you've already saw, the bookkeeping you'll have to do will negate any performance you may gain by avoiding pointers.

Here's a very barebones doubly-linked list layout, which implements the bare minimum required and can be used for any data if you don't mind casting:

Code: Select all

type _
  Node
  
  as any ptr _
    _data
  as Node ptr _
    _next, _
    _previous
end type

type _
  LinkedList
  
  declare destructor()
  
  as Node ptr _
    first, _
    last
  
  declare property _
    empty() as boolean
  
  declare function _
    addFirst( _
      byval as any ptr ) _
    as Node ptr
  declare function _
    addLast( _
      byval as any ptr ) _
    as Node ptr
  declare function _
    addBefore( _
      byval as Node ptr, _
      byval as any ptr ) _
    as Node ptr
  declare function _
    addAfter( _
      byval as Node ptr, _
      byval as any ptr ) _
    as Node ptr
  declare function _
    removeLast() as any ptr
  declare function _
    removeFirst() as any ptr
  declare function _
    remove( _
      byval as Node ptr ) _
    as any ptr
end type

/'
  The destructor needs only to delete the nodes in the
  linked list. Since the nodes themselves aren't meant to
  *store* actual data, but pointers to them, deleting the
  data itself is not required.
'/
destructor _
  LinkedList()
  
  var _
    n => first
  
  do while( n <> 0 )
    var _
      tmp => n->_next
    
    delete( n )
    
    n => tmp
  loop
end destructor

property _
  LinkedList.empty() _
  as boolean
  
  return( cbool( first = 0 andAlso last = 0 ) )
end property

function _
  LinkedList.addBefore( _
    byval aNode as Node ptr, _
    byval aData as any ptr ) _
  as Node ptr
  
  var _
    newNode => new Node
  
  newNode->_data => aData
  newNode->_next => aNode
  newNode->_previous => aNode->_previous
  aNode->_previous => newNode
  
  if( aNode->_previous = 0 ) then
    first => newNode
  end if
  
  return( newNode )
end function

function _
  LinkedList.addAfter( _
    byval aNode as Node ptr, _
    byval aData as any ptr ) _
  as Node ptr
  
  var _
    newNode => new Node
  
  newNode->_data => aData
  newNode->_previous => aNode
  newNode->_next => aNode->_next
  aNode->_next => newNode
  
  if( aNode->_next = 0 ) then
    last => newNode
  end if
  
  return( newNode )
end function

function _
  LinkedList.addFirst( _
    byval aData as any ptr ) _
  as Node ptr
  
  var _
    newNode => new Node
  
  newNode->_data => aData
  newNode->_previous => 0
  newNode->_next => first
  
  if( first = 0 ) then
    last => newNode
  else
    first->_previous => newNode
  end if
  
  first => newNode
  
  return( newNode )
end function

function _
  LinkedList.addLast( _
    byval aData as any ptr ) _
  as Node ptr
  
  var _
    newNode => new Node
  
  newNode->_data => aData
  newNode->_previous => last
  newNode->_next => 0
  
  if( last = 0 ) then
    first => newNode
  else
    last->_next => newNode
  end if
  
  last => newNode
  
  return( newNode )
end function

function _
  LinkedList.remove( _
    byval aNode as Node ptr ) _
  as any ptr
  
  if( aNode->_previous = 0 ) then
    first => aNode->_next
    first->_previous => 0
  elseif( aNode->_next = 0 ) then
    last => aNode->_previous
    last->_next => 0
  else
    aNode->_previous->_next => aNode->_next
    aNode->_next->_previous => aNode->_previous
  end if
  
  dim as any ptr _
    tmp
  
  if( aNode <> 0 ) then
    tmp => aNode->_data
    delete( aNode )
  end if
  
  return( tmp )
end function

function _
  LinkedList.removeFirst() _
  as any ptr
  
  if( first = last ) then
    var _
      tmp => first->_data
    
    delete( first )
    
    first => 0
    last => 0
    
    return( tmp )
  else
    return( remove( first ) )
  end if
end function

function _
  LinkedList.removeLast() _
  as any ptr
  
  if( first = last ) then
    var _
      tmp => last->_data
    
    delete( last )
    
    first => 0
    last => 0
    
    return( tmp )
  else
    return( remove( last ) )
  end if
end function
It uses pointers, but refactoring it to use handles should be trivial: just replace the pointer operations with array operations and you're done.
olympic sleeper
Posts: 41
Joined: Jun 07, 2020 15:47

Re: Any suggestions on the best way to set up a linked list?

Post by olympic sleeper »

Many thanks for the suggestion. I have been doing some pondering on this and I am beginning to realise how deep this rabbit hole I have made myself could be.

I thought that by using some kind of linked (or indeed other list structure) would enable me to handle 2 things;
  • Objects that are in others which are being moved by the player, say a sack containing other things
    Objects that in things that are on things, say a coin in a box on a shelf
So if the player gets the box and puts it in the sack I won’t care what’s in the box, I just move the box's location to the sacks and add it to the sack's 'inside' list (object.objects_in_ptr). Equally if the player gets something from the sack I just move that objects location where-ever and change the sacks list so that it no-longer links to the object.

Except…

I haven’t got a clue how to navigate such a list. Here’s an example location to show how muddled I am.

You are in a bank, by the far wall there is a safe and on the safe there is a cash box containing a coin. Inside the safe there is a metal shelf and on that there is a bag containing a gem.

So here we have one object (the safe) which has things in it (the shelf and on that is a bag) and on the safe – the box.

To describe the room I was planning to loop through each of the object's in the room starting with the link to the 1st from the room structure (rooms.object_ptr). However I have no idea, and at present no way of knowing, how many objects contain others or are on others. Thus I cannot work out how to structure the code so it loops through all the things in the room showing for each what they contain, what those might contain upto object x, or anything that is on anything else is on and so on.

If we carry on with the scenario, suppose the player takes the bag, we move the bag’s location to their inventory and update the safe’s ‘inside’ list.

Then they take the box, so again simple, update the box’s location and the safe’s ‘what’s on it’ list.

Now the player puts the box in the bag, again no problem as before change the box’s location to the bag, add the box to the bags ‘inside list’.

Now the player puts the bag back into the safe and describe the room.

You are in a bank, by the far wall there is a safe. Inside the safe there is a metal shelf and on that there is a bag containing a box and a gem, inside the box there is a coin.

Now there are more things in the safe than on it so I cannot use a fixed number of loops since I do not know how many things might be on or inside or a combination of anything else and am staring at loops within loops within loops with no way of figuring out how to show what’s in what or on what. It all sounds horribly recursive

Suppose the player has a shirt, they take the bag, put the shirt in the safe and the bag on the shirt. Ouch.

I suspect my structures might be wrong for this, but don't really know what they should be in order to untangle it. I might(?) need some way of recursivly call some kind of sub that allows me to run though each of the objects, what they hold and where they are in such a way that it generates moderatly good English but needless to say I am baffled as to where to even beguin on that.

Any help will be hugely appreciated.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Any suggestions on the best way to set up a linked list?

Post by paul doe »

A very simple usage example, iterating the list of objects contained within a room:

Code: Select all

type _
  Room
  
  declare constructor( _
    byref as const string )
  declare destructor()
  
  as string _
    description
  
  '' The list of objects in this room
  as LinkedList _
    objects
end type

constructor _
  Room( _
    byref aDescription as const string )
  
  description => aDescription
end constructor

destructor _
  Room()
end destructor

type _
  MyObject
  
  declare constructor( _
    byref as const string )
  declare destructor()
  
  as string _
    name
  
  '' The room this object is currently on
  as Room ptr _
    room
  
  /'
    If this object is a container (say, a chest), this list will
    have all the objects within.
  '/
  as LinkedList _
    containedObjects
end type

constructor _
  MyObject( _
    byref aName as const string )
  
  name => aName
end constructor

destructor _
  MyObject()
end destructor

sub _
  DisplayRoom( _
    byval aRoom as Room ptr )
  
  ? "You are in " & aRoom->description
  ?
  ? "Here, you can see: "
  
  var _
    n => aRoom->objects.first
  
  do while( n <> 0 )
    ? cast( MyObject ptr, n->_data )->name
    
    n => n->_next
  loop
end sub

dim as Room _
  rooms( ... ) => { _
    ( "A large room" ), ( "A dormitory" ), ( "The main hall" ), ( "A closet" ) }
dim as MyObject _
  objects( ... ) => { _
    ( "Pendant" ), ( "Jar" ), ( "Broom" ), ( "Brush" ), ( "Chair" ) }

'' We'll put the Pendant and the Jar in the large room...
with rooms( 0 ).objects
  .addLast( @objects( 0 ) )
  .addLast( @objects( 1 ) )
end with

'' ...the Brush in the dormitory...
rooms( 1 ).objects.addLast( @objects( 3 ) )

'' ...The Chair in the main hall...
rooms( 2 ).objects.addLast( @objects( 4 ) )

'' ...and the Broom in the closet
rooms( 3 ).objects.addLast( @objects( 2 ) )

'' Display the data for a room
DisplayRoom( @rooms( 0 ) )

sleep()
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Any suggestions on the best way to set up a linked list?

Post by paul doe »

olympic sleeper wrote:Many thanks for the suggestion. I have been doing some pondering on this and I am beginning to realise how deep this rabbit hole I have made myself could be.
...
Yes and no. Yes because it is indeed a pretty messy problem; No because it can be tackled in a reasonable way. Before I give further advice, are you willing to use Object-Oriented techniques, or do you want to tackle it in procedural form? I seem to recall you've said you know C, so perhaps procedural it is?
Tourist Trap
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: Any suggestions on the best way to set up a linked list?

Post by Tourist Trap »

olympic sleeper wrote:Hi,

I am strugging to remember how to set up a linked list.
Hi olympic sleeper,

Here is an example of mine that looks like what you are trying. It's bones that are linked list with some graphical sugar:

Code: Select all

 ''--------------------------------------------------
''  "funky swimmer demo" to test the bones udt     
''--------------------------------------------------


#define   _pi            (4*aTn(1))
#define _MIN(a, b)      iif((a)<(b), (a), (b))
#define _MAX(a, b)      iif((a)>(b), (a), (b))


type LENGTH
      as single      _lengthValue
end type


type ANGLEOXY
      as single      _angleValue
end type


type POSITIONXY
      as single      _x
      as single      _y
end type


type ORIENTATION
      as ANGLEOXY      _angleOxy
end type


type BONEPARAMETER
      as integer         _boneHierarchyRank
      as POSITIONXY      _bonePivotPosition
      as LENGTH         _boneLength
      as ORIENTATION      _boneOrientation
end type

type BONEPARENT      as BONE ptr
type BONECHILD      as BONE ptr
type BONE
   declare constructor()
   declare destructor()
   declare property BonePivot() as POSITIONXY
   declare property BoneEnd() as POSITIONXY
   declare property BoneLength() as LENGTH
   declare property BoneOrientation() byref as single
   declare property BoneOrientation(byval as single)
   'hierarchy
   declare sub DefineBoneLength(byref L as const LENGTH)
   declare sub AttachBoneToParentBone(byval P as BONEPARENT=0, _
                              byref XY as POSITIONXY=type<POSITIONXY>(0,0))
   declare sub RefreshHierarchy()
   declare sub UpdateFixHierarchy()
      as BONEPARENT      _parent
      as BONECHILD      _child(any)
      as BONEPARAMETER   _parameter
   'interaction
   declare function DistanceToTubeFrom overload(byref Xy as const POSITIONXY) as single
   declare function DistanceToTubeFrom(byref X as const single, _
                              byref Y as const single) _
                              as single
   declare sub TestMouse()
      as integer         _detectionScreenDistanceToAxis
      as boolean         _hasMouseOver
      as boolean         _hasMouseOverAxis
      as boolean         _hasMouseOverTube
   'visualization
   declare sub DrawBone()
   declare sub DrawBoneDetectionTube()
      as ulong         _defaultColor
      as ulong         _mouseOverColor
      as ulong         _mouseOverDetectionTubeColor
end type
constructor BONE()
   if screenPtr=0 then
      dim as integer   deskX, deskY
         screenInfo   deskX, deskY
      windowTitle "Bone is a 32bits color gui object"
      screenRes 0.6*deskX, 0.6*deskY, 32
   end if
   with THIS
      'hierarchy
   end with
   with THIS
      'interaction
      ._detectionScreenDistanceToAxis   => 4
      ._hasMouseOver               => FALSE
   end with
   with THIS
      'visualization
      ._defaultColor               => rgb(220,200,140)
      ._mouseOverColor            => rgb(100,240,240)
      ._mouseOverDetectionTubeColor   => rgb(100,200,240)
   end with
end constructor
destructor BONE()
   if THIS._parent<>0 then
      for index as integer =   lBound(THIS._child) to _
                        uBound(THIS._child)
         THIS._child(index)->_parent = THIS._parent
      next index
   end if
end destructor
property BONE.BonePivot() as POSITIONXY
   return THIS._parameter._bonePivotPosition
end property
property BONE.BoneEnd() as POSITIONXY
   var returnValue   =>   THIS._parameter._bonePivotPosition
   with THIS._parameter
      returnValue._x   +=   cos(._boneOrientation._angleOxy._angleValue)*._boneLength._lengthValue
      returnValue._y   +=   sin(._boneOrientation._angleOxy._angleValue)*._boneLength._lengthValue
   end with
   '
   return returnValue
end property
property BONE.BoneLength() as LENGTH
   return THIS._parameter._boneLength
end property
property BONE.BoneOrientation() byref as single
   return THIS._parameter._boneOrientation._angleOxy._angleValue
end property
property BONE.BoneOrientation(byval SetValue as single)
   THIS._parameter._boneOrientation._angleOxy._angleValue = SetValue
end property
sub BONE.DefineBoneLength(byref L as const LENGTH)
   with THIS
      with ._parameter
         ._boneLength      => L
      end with
   end with
   'refresh child position
   for index as integer =   lBound(THIS._child) to _
                     uBound(THIS._child)
      THIS._child(index)->_parameter._bonePivotPosition = THIS.BoneEnd
   next index
end sub
sub BONE.AttachBoneToParentBone(byval P as BONEPARENT=0, _
                        byref XY as POSITIONXY=type<POSITIONXY>(0,0))
   if P<>0 then
      THIS._parent   => P
      redim preserve P->_child(uBound(P->_child) - lBound(P->_child) + 1)
      P->_child(uBound(P->_child) - lBound(P->_child)) => @THIS
      P->_child(uBound(P->_child) - lBound(P->_child))->_parameter._bonePivotPosition = P->BoneEnd
   end if
end sub
sub BONE.RefreshHierarchy()
   for index as integer =   lBound(THIS._child) to _
                     uBound(THIS._child)
      THIS._child(index)->_parameter._bonePivotPosition = THIS.BoneEnd
   next index
end sub
sub BONE.UpdateFixHierarchy()
   var index   => lBound(THIS._child)
   while index<=uBound(THIS._child)
      if THIS._child(index)=0 then
         swap   THIS._child(index), _
               THIS._child(uBound(THIS._child))
         if (uBound(THIS._child) - lBound(THIS._child))>0 then
            redim preserve THIS._child(uBound(THIS._child) - lBound(THIS._child) - 1)
         else
            erase THIS._child
         end if
      else
         index += 1
      end if
   wend
end sub
function BONE.DistanceToTubeFrom(byref Xy as const POSITIONXY) as single
   var byref angle      => THIS._parameter._boneOrientation._angleOxy._angleValue
   var byref xPivot   => THIS._parameter._bonePivotPosition._x
   var byref yPivot   => THIS._parameter._bonePivotPosition._y
   '
   return _
   abs( Xy._x*sin(angle) - Xy._y*cos(angle) + yPivot*cos(angle) - xPivot*sin(angle) )
end function
function BONE.DistanceToTubeFrom(byref X as const single, _
                         byref Y as const single) _
                         as single
   var byref angle      => THIS._parameter._boneOrientation._angleOxy._angleValue
   var byref xPivot   => THIS._parameter._bonePivotPosition._x
   var byref yPivot   => THIS._parameter._bonePivotPosition._y
   '
   return _
   abs( X*sin(angle) - Y*cos(angle) + yPivot*cos(angle) - xPivot*sin(angle) )
end function
sub BONE.TestMouse()
   dim as integer   gmX, gmY, gmWheel, gmBtn
   var errorCode   => getMouse(gmX, gmY, gmWheel, gmBtn)
   if errorCode<>0 then exit sub
   '
   var byref yPivot   => THIS._parameter._bonePivotPosition._y
   var byref yEnd      => THIS.BoneEnd._y
   var distanceToBoneAxis => THIS.DistanceToTubeFrom(cSng(gmX), cSng(gmY))
   if distanceToBoneAxis<THIS._detectionScreenDistanceToAxis   andAlso _
      gmY>_MIN(yPivot, yEnd)                           andAlso _
      gmY<_MAX(yPivot, yEnd)                           then
      if distanceToBoneAxis<1 then
         if not THIS._hasMouseOverAxis then THIS._hasMouseOverAxis = TRUE
      else
         if THIS._hasMouseOverAxis then THIS._hasMouseOverAxis = FALSE
      end if
      if not THIS._hasMouseOverTube then THIS._hasMouseOverTube = TRUE
      if not THIS._hasMouseOver andAlso _
         (THIS._hasMouseOverAxis orElse THIS._hasMouseOverTube) then
         THIS._hasMouseOver = TRUE
      end if
   else
      if THIS._hasMouseOverAxis then THIS._hasMouseOverAxis = FALSE
      if THIS._hasMouseOverTube then THIS._hasMouseOverTube = FALSE
      if THIS._hasMouseOver then THIS._hasMouseOver = FALSE
   end if
end sub
sub BONE.DrawBone()
   THIS.TestMouse()
   '
   line(THIS.BonePivot._x, THIS.BonePivot._y) - _
      (THIS.BoneEnd._x, THIS.BoneEnd._y), _
      THIS._defaultColor
   for index as integer =   lBound(THIS._child) to _
                     uBound(THIS._child)
      THIS._child(index)->DrawBone()
   next index
   if THIS._hasMouseOver then
      line(THIS.BonePivot._x, THIS.BonePivot._y) - _
         (THIS.BoneEnd._x, THIS.BoneEnd._y), _
         THIS._mouseOverColor
   end if
end sub
sub BONE.DrawBoneDetectionTube()
   THIS.TestMouse()
   '
   var angle   => THIS._parameter._boneOrientation._angleOxy._angleValue + 2*aTn(1)
   if THIS._hasMouseOverTube then
      for t as integer = -THIS._detectionScreenDistanceToAxis to _
                     THIS._detectionScreenDistanceToAxis
         line(THIS.BonePivot._x + t*cos(angle), THIS.BonePivot._y + t*sin(angle)) - _
            (THIS.BoneEnd._x + t*cos(angle), THIS.BoneEnd._y + t*sin(angle)), _
            THIS._mouseOverDetectionTubeColor
      next t
   else
      for t as integer = -THIS._detectionScreenDistanceToAxis to _
                     THIS._detectionScreenDistanceToAxis
         line(THIS.BonePivot._x + t*cos(angle), THIS.BonePivot._y + t*sin(angle)) - _
            (THIS.BoneEnd._x + t*cos(angle), THIS.BoneEnd._y + t*sin(angle)), _
            0
      next t
   end if
   if THIS._hasMouseOverAxis then
      line(THIS.BonePivot._x, THIS.BonePivot._y) - _
         (THIS.BoneEnd._x, THIS.BoneEnd._y), _
   THIS._mouseOverColor
   else
      line(THIS.BonePivot._x, THIS.BonePivot._y) - _
         (THIS.BoneEnd._x, THIS.BoneEnd._y), _
         THIS._defaultColor
   end if
end sub


'>xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxMAINxxx

'>---------------------------------------------------INIT___
screen 18, 32
color , rgb(100,090,140)

'build every bones and attachments
dim as BONE      headBone
dim as BONE      bodyTorseBone
dim as BONE      bodyStomachBone
dim as BONE      bodyUpperArm1
dim as BONE      bodyUpperArm2
dim as BONE      bodyLowerArm1
dim as BONE      bodyLowerArm2
dim as BONE      bodyUpperLeg1
dim as BONE      bodyUpperLeg2
dim as BONE      bodyLowerLeg1
dim as BONE      bodyLowerLeg2
dim as BONE      bodyFoot1
dim as BONE      bodyFoot2
with headBone
   .BoneOrientation            => +_pi/2
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(12))
end with
with bodyTorseBone
   .BoneOrientation            => +_pi/2 + .1
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(18))
   .AttachBoneToParentBone(@headBone)
end with
with bodyStomachBone
   .BoneOrientation            => +_pi/2
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(18))
   .AttachBoneToParentBone(@bodyTorseBone)
end with
with bodyUpperArm1
   .BoneOrientation            => +2*_pi/3
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(24))
   .AttachBoneToParentBone(@headBone)
end with
with bodyLowerArm1
   .BoneOrientation            => +2*_pi/3 - .2
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(12))
   .AttachBoneToParentBone(@bodyUpperArm1)
end with
with bodyUpperArm2
   .BoneOrientation            => +_pi/3
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(24))
   .AttachBoneToParentBone(@headBone)
end with
with bodyLowerArm2
   .BoneOrientation            => +_pi/3 - .2
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(12))
   .AttachBoneToParentBone(@bodyUpperArm2)
end with
with bodyUpperLeg1
   .BoneOrientation            => +_pi/3
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(28))
   .AttachBoneToParentBone(@bodyStomachBone)
end with
with bodyLowerLeg1
   .BoneOrientation            => +_pi/3 + .2
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(26))
   .AttachBoneToParentBone(@bodyUpperLeg1)
end with
with bodyFoot1
   .BoneOrientation            => bodyLowerLeg1.BoneOrientation - _pi/2
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(6))
   .AttachBoneToParentBone(@bodyLowerLeg1)
end with
with bodyUpperLeg2
   .BoneOrientation            => +2*_pi/3 - .2
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(28))
   .AttachBoneToParentBone(@bodyStomachBone)
end with
with bodyLowerLeg2
   .BoneOrientation            => +2*_pi/3 + .2
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(26))
   .AttachBoneToParentBone(@bodyUpperLeg2)
end with
with bodyFoot2
   .BoneOrientation            => bodyLowerLeg2.BoneOrientation - _pi/2
   ._parameter._bonePivotPosition   => type(320, 120)
   .DefineBoneLength(type(6))
   .AttachBoneToParentBone(@bodyLowerLeg2)
end with


'>---------------------------------------------------LOOP___
var keyPressed   => inkey()
dim as single   orientationStep   => .008
do
   headBone._parameter._bonePivotPosition   => type(320 + 100*sin(bodyTorseBone.BoneOrientation), 120)
   'some displacement
   (bodyTorseBone.BoneOrientation) -= orientationStep*4
   (bodyStomachBone.BoneOrientation) = bodyTorseBone.BoneOrientation + _pi/3
   (bodyLowerLeg2.BoneOrientation) = bodyTorseBone.BoneOrientation + _pi/3
   (bodyUpperArm1.BoneOrientation) = bodyTorseBone.BoneOrientation - headBone._parameter._bonePivotPosition._x/10
   (bodyLowerArm1.BoneOrientation) = bodyTorseBone.BoneOrientation + headBone._parameter._bonePivotPosition._x/10
   (bodyUpperArm2.BoneOrientation) = bodyTorseBone.BoneOrientation - headBone._parameter._bonePivotPosition._x/100
   '
   'keep the bones together
   ':todo: a single command to refresh all the bones of a given hierarchy
   headBone.RefreshHierarchy()
   bodyTorseBone.RefreshHierarchy()
   bodyStomachBone.RefreshHierarchy()
   bodyUpperArm1.RefreshHierarchy()
   bodyUpperArm2.RefreshHierarchy()
   bodyUpperLeg1.RefreshHierarchy()
   bodyUpperLeg2.RefreshHierarchy()
   bodyLowerLeg1.RefreshHierarchy()
   bodyLowerLeg2.RefreshHierarchy()
   '
   'draw bones
   screenLock()
      cls
      circle (320 + 100*sin(bodyTorseBone.BoneOrientation), 120), 4
      ? "funky swimmer demo"
      ? bodyTorseBone.BoneOrientation
      '
      headBone.DrawBone()
      bodyTorseBone.DrawBone()
      bodyStomachBone.DrawBone()
      bodyUpperArm1.DrawBone()
      bodyUpperArm2.DrawBone()
      bodyLowerArm1.DrawBone()
      bodyLowerArm2.DrawBone()
      bodyUpperLeg1.DrawBone()
      bodyUpperLeg2.DrawBone()
      bodyLowerLeg1.DrawBone()
      bodyLowerLeg2.DrawBone()
      bodyFoot1.DrawBone()
      bodyFoot2.DrawBone()
   screenUnlock()
   '
   'if keypressed=esc then quit
   keyPressed   => inkey()
   sleep 15
loop until keyPressed=chr(27)


'>yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyEND.yyy
getKey()

'(eof)
The key feature lies here:
type BONEPARENT as BONE ptr
type BONECHILD as BONE ptr
type BONES
.....as BONEPARENT _parent
.....as BONECHILD _child(any)
end type
olympic sleeper
Posts: 41
Joined: Jun 07, 2020 15:47

Re: Any suggestions on the best way to set up a linked list?

Post by olympic sleeper »

Hi,

Many thanks for the help. A quick explanation of my level of coding experience, which I hope will help with folk suggesting ideas, all of which are welcome even if I suspect I will not understand some.

I worked for many years as a C programmer writing multi-user requester server applications, but and it is a big but, that was a very long time ago. So while I can remember some stuff (pointers, memory allocation, structures, procedures, conditions - I still forget the then in Basic if statements and find myself bracketing them - etc.) and general coding practices, I am very, very rusty. Hence my posting in the beginners forum as to be honest that is where I feel my experience now leaves me. My Basic experience is even more neolithic, but I picked this up again (rather than C or a 'newer more whizzy' language as I kinda like it and the string handling does not feel like the afterthought is does in C.

I have written a few very simple routines in visual basic (Excel macros mainly) so a know a very limited amount on object-oriented code but know nothing about the more complex areas of Free Basic. So sadly Tourist Trap, your code while welcome is beyond me, sorry.

Since my initial post I have been trying to work on a list building routine. It is not fancy, it probably does not work – I haven't tried it and its not finished, but perhaps it will give a further idea of where I am in my lack of knowledge.

All vars are integers with the exception of objects(i).name and objects(i).long_name which are strings.

Code: Select all

for i =1 to num_objects
	read objects(i).name,objects(i).long_name,objects(i).additional_desc,objects(i).location,objects(i).weight,objects(i).size,objects(i).description,objects(i).hold_size,objects(i).surface_size,objects(i).status,objects(i).cloth_type
	
	print objects(i).long_name;
	if objects(i).location >0 and objects(i).weight>0 then		'if object is just in a room and not in or on or under etc 
												'something else and it is not fixed (weight=0)
		print " in ";objects(i).location
		if rooms(objects(i).location).object_ptr=0 then 				'if the object pointer for the room the object is in is not set then
			rooms(objects(i).location).object_ptr=i				'set the rooms 1st object pointer
			print "set room ";objects(i).location;" to ";objects(i).name
		else												'otherwise	
			temp=rooms(objects(i).location).object_ptr			'store the object number in temp
			while objects(temp).next_object_ptr<>0				'while the objects next object pointer is set
			print "Adding ";objects(temp).long_name;" to ";objects(i).location
				temp=objects(temp).next_object_ptr				'find the number of the object thats being pointed to and store in temp
			wend
			objects(temp).next_object_ptr=i					'at the end of the above loop temp will hold the 
														'number of the last object in the list, so add this one to its link
			print "temp is pointing to ";objects(temp).name
		end if
So thank you again and I look forward to suggestions, I think I'd prefer ideas and code segments rather than full routines as this will help me learn but any help is gratefully received.
grindstone
Posts: 862
Joined: May 05, 2015 5:35
Location: Germany

Re: Any suggestions on the best way to set up a linked list?

Post by grindstone »

Looks like you're working to write an adventure game, right? In this case, using a linked list would be a pretty good idea.
olympic sleeper
Posts: 41
Joined: Jun 07, 2020 15:47

Re: Any suggestions on the best way to set up a linked list?

Post by olympic sleeper »

grindstone wrote:Looks like you're working to write an adventure game, right? In this case, using a linked list would be a pretty good idea.
Hi,

Not quite. It is an adventure but the structure is more a forest of n trees (rooms) with each tree having n branches for the objects in each room. Each object has a maximum of n^3 branches as each could have n objects on it (n^1), n objects in it (n^2) and n objects under it (so n^3). Each of these objects could again have n^3 branches as each could also have n objects on it, n under it and n on it. I tried to draw this and gave up.

In practice the objects will be restricted on what they can hold by a size for their inside and surface. At present I'm not sure how to handle under and may just restrict this to 1 (to hide keys under mats etc.). Equally I will need a way to prevent a splurge of objects if the player enters a shop, just initially describing the type of shelves or something rather than every single object on every single shelf. However that is for the future.

Its horrible to explain and I haven't a clue how to write code that'll navigate it, what I have right now is a mess.
Lost Zergling
Posts: 534
Joined: Dec 02, 2011 22:51
Location: France

Re: Any suggestions on the best way to set up a linked list?

Post by Lost Zergling »

Hello. Sounds pretty hard. I m not sure I could do something like what you expect. I think you shall perhaps try FIRST to design and/or conceptualize an "object model", something can be written and understood on a paper. Have a look to LZLE project. Consider using lists as private inside objects or shared between objects, just as technical tool. Consider also data exchanges between objects (ie data exchanges between lists also('snatch')). Try to clarfy objects behaviour. … Can t provide more advice, huge work ahead, I m not in game design, sorry.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Any suggestions on the best way to set up a linked list?

Post by paul doe »

olympic sleeper wrote:...
Not quite. It is an adventure but the structure is more a forest of n trees (rooms) with each tree having n branches for the objects in each room. Each object has a maximum of n^3 branches as each could have n objects on it (n^1), n objects in it (n^2) and n objects under it (so n^3). Each of these objects could again have n^3 branches as each could also have n objects on it, n under it and n on it. I tried to draw this and gave up.
...
My, doesn't this sounds delightfully complicated for a 'comeback' project? ;)

What I mean is, from a design standpoint, this sounds terribly convoluted. If you couldn't conceptualize (draw) it, perhaps you're getting into deeper trouble than needed? Isn't a simpler design possible, that also conveys your vision?

So, I'll consider this topic 'solved' so as not to derail it, since I already provided 'a way' (not 'the best way') to set up a linked list. You may want to open a topic on 'Projects', so you can discuss implementation/data representation issues in greater detail?
grindstone
Posts: 862
Joined: May 05, 2015 5:35
Location: Germany

Re: Any suggestions on the best way to set up a linked list?

Post by grindstone »

Alright, let's do it step by step. As a start a very basic first approach to create and handle a double linked list representing a tree structure. You can create an arbitrary number of rooms and walk through them:

Code: Select all

Type tRoom
	Dim As Integer level
	Dim As Integer roomNumber
	Dim As tRoom Ptr parent 'pointer to parent room
	Dim As tRoom Ptr child(Any) 'array of subrooms
	Declare Destructor
	Declare Sub createChild
End Type

Destructor tRoom 'delete this room and all subbranches
	If UBound(child) >= 0 Then
		For x As Integer = 0 To UBound(child)
			If child(x) <> 0 Then
				Delete child(x)
				child(x) = 0
			EndIf
		Next
		ReDim child(-1)
	EndIf
End Destructor

Sub tRoom.createChild 'create a new child room
	Dim As Integer x = UBound(child) + 1 'next index
	ReDim Preserve this.child(x) 'extend child array
	
	this.child(x) = New tRoom 'create new room instance
	this.child(x)->parent = @This 'pointer to the parent room
	this.child(x)->level = this.level + 1 'next level
	this.child(x)->roomNumber = x 'number of  the new room
	
End Sub

Function walk(currentRoom As tRoom Ptr) As tRoom Ptr
	Dim As Integer x, y, cmax
	Dim As String g
	
	Do
		Cls
		Print "You are in room number";currentRoom->roomNumber; " of level"; currentRoom->level;"."
		Print
		Print "What do you want to do?"
		Print
		Print , " C = create a new subroom"
		For x = 0 To UBound(currentRoom->child)
			Print , x; " = go to room number"; x
		Next
		Print , " B = go back to the previous room"
		cmax = UBound(currentRoom->child)
		Do
			g = InKey
			Select Case g
				Case "c"
					currentRoom->createChild
					Exit Do
				Case "b"
					Return currentRoom->parent
				Case Else
					For x = 0 To cmax
						If g = Str(x) Then
							Return currentRoom->child(x)
						EndIf
					Next
			End Select
		Loop
	Loop

End Function

Dim As tRoom Ptr root, rp
Dim As Integer x

'create the 1st room of the tree
root = New tRoom
root->level = 1
root->roomNumber = 0

rp = root
Do 'take a little walk through the rooms
	rp = walk(rp)
Loop While rp

Delete root 'delete the root room an all subrooms

? "OK"

Sleep
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: Any suggestions on the best way to set up a linked list?

Post by BasicCoder2 »

You seemed to have concluded a linked list is the solution to how to represent this "world"? To me you seem to be describing a tree structure. The trunk is "everything" and branch nodes are things that contain things or spatial relationships. It reminds me of semantic networks and frames.
http://www.cse.unsw.edu.au/~billw/cs941 ... rames.html
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Any suggestions on the best way to set up a linked list?

Post by paul doe »

A valid conclusion, since both arrays and linked lists can be used to represent all the other, more complex data structures:

Code: Select all

#include once "linked-list.bi" '' The code I presented before

type _
  TreeNode
  
  public:
    declare constructor( _
      byref as const string )
    declare destructor()
    
    '' Pure convenience
    declare function _
      add( _
        byval as TreeNode ptr ) _
      as TreeNode ptr
    
    as string _
      name
    as TreeNode ptr _
      parent
    as LinkedList _
      childNodes
end type

constructor _
  TreeNode( _
    byref aName as const string )
  
  name => aName
end constructor

destructor _
  TreeNode()
  
  do while( not childNodes.empty )
    var _
      n => childNodes.removeFirst()
    
    delete( cast( TreeNode ptr, n ) )
  loop
end destructor

function _
  TreeNode.add( _
    byval aNode as TreeNode ptr ) _
  as TreeNode ptr
  
  childNodes.addLast( aNode )
  aNode->parent => @this
  
  return( aNode )
end function

'' Displays the tree recursively
sub _
  showNode( _
    byval aNode as TreeNode ptr, _
    byval depth as integer => 0 )
  
  ? string( depth * 2, " " ) & aNode->name
  
  var _
    n => aNode->childNodes.first
  
  do while( n <> 0 )
    showNode( n->_data, depth + 1 )
    
    n => n->_next
  loop
end sub

scope
  '' Create a tree
  var _
    root => TreeNode( "Root" )
  
  root _
    .add( new TreeNode( "Child1" ) ) _
      ->add( new TreeNode( "Child1" ) ) _
        ->add( new TreeNode( "Child1" ) )->parent _
        ->add( new TreeNode( "Child2" ) ) _
          ->add( new TreeNode( "Child1" ) )->parent->parent->parent _
      ->add( new TreeNode( "Child2" ) )->parent _
      ->add( new TreeNode( "Child3" ) )->parent->parent _
    ->add( new TreeNode( "Child2" ) )
  
  '' And display it
  showNode( @root )
end scope

sleep()
@olympic sleeper: the above code uses the linked list implementation from before. All you need to do is save it on a file (here called linked-list.bi), and put it in the same folder as this code. Traditionally, headers in FreeBasic (and other BASIC dialects) use the .bi extension. The output is thus:

Code: Select all

Root
  Child1
    Child1
      Child1
      Child2
        Child1
    Child2
    Child3
  Child2
By modifying the above code, you can also have trees with multiple roots, binary trees, and any other structure of arbitrary complexity.

PS: I'm fully aware of the shortcomings of the code. It is meant to be a simple example, not a fully working tree implementation.
Post Reply