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?

Postby olympic sleeper » Jun 18, 2020 9:36

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: 326
Joined: Dec 02, 2011 22:51
Location: France

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

Postby Lost Zergling » Jun 18, 2020 10:14

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
Posts: 1255
Joined: Jul 25, 2017 17:22
Location: Argentina

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

Postby paul doe » Jun 18, 2020 16:16

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?

Postby olympic sleeper » Jun 18, 2020 16:26

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
Posts: 1255
Joined: Jul 25, 2017 17:22
Location: Argentina

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

Postby paul doe » Jun 18, 2020 16:29

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
Posts: 1255
Joined: Jul 25, 2017 17:22
Location: Argentina

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

Postby paul doe » Jun 18, 2020 16:41

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: 2901
Joined: Jun 02, 2015 16:24

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

Postby Tourist Trap » Jun 18, 2020 16:46

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?

Postby olympic sleeper » Jun 18, 2020 19:58

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: 744
Joined: May 05, 2015 5:35
Location: Germany

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

Postby grindstone » Jun 18, 2020 23:04

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?

Postby olympic sleeper » Jun 19, 2020 10:08

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: 326
Joined: Dec 02, 2011 22:51
Location: France

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

Postby Lost Zergling » Jun 19, 2020 10:48

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
Posts: 1255
Joined: Jul 25, 2017 17:22
Location: Argentina

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

Postby paul doe » Jun 19, 2020 14:57

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: 744
Joined: May 05, 2015 5:35
Location: Germany

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

Postby grindstone » Jun 19, 2020 20:44

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: 3577
Joined: Jan 01, 2009 7:03
Location: Australia

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

Postby BasicCoder2 » Jun 19, 2020 21:03

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
Posts: 1255
Joined: Jul 25, 2017 17:22
Location: Argentina

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

Postby paul doe » Jun 20, 2020 4:12

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.

Return to “Beginners”

Who is online

Users browsing this forum: No registered users and 3 guests