* * *

Author Topic: Game Contest 2018  (Read 45841 times)

mrguzgog

  • Jr. Member
  • **
  • Posts: 71
Re: Game Contest 2018
« Reply #75 on: January 31, 2018, 08:40:47 pm »
Haha, great name, it looks fine and don't forget poor people with Windows later :)

Btw. my game is crashing on Linux even under WINE :)

Hehe, I'm not going to even think about compiling on Windows until it's finished  :)

What library or framework are you using?

I've now got 'levels' sorted and done some more tidying but it's still code-spaghetti in here  :o







Paul_

  • Full Member
  • ***
  • Posts: 106
Re: Game Contest 2018
« Reply #76 on: February 01, 2018, 01:16:41 am »
I'm using SFML (https://github.com/DJMaster/csfml-fpc)

It will work after some code polishing. I just wonder why it's crashing WINE :)
« Last Edit: February 01, 2018, 01:19:05 am by Paul_ »

Eugene Loza

  • Hero Member
  • *****
  • Posts: 561
    • My "almost daily" development blog
Re: Game Contest 2018
« Reply #77 on: February 01, 2018, 07:07:15 am »
I just wonder why it's crashing WINE :)
Because Wine is really no panacea :) And personally some time ago I found that my distro repository had a very outdated version of Wine, so I got the freshest version from the WineHQ and it worked better. Compare the version you're using with the upstream.
Lazarus 1.9 + FPC 3.1.1 Debian Jessie 64 bit.

My Free and Open Source games in Lazarus/FreePascal/CastleGameEngine:
https://decoherence.itch.io/
(and some ancient games in Turbo Pascal too)
Sources are here: https://github.com/eugeneloza?tab=repositories

Paul_

  • Full Member
  • ***
  • Posts: 106
Re: Game Contest 2018
« Reply #78 on: February 01, 2018, 04:31:33 pm »
Thanks for good tip, with actual version from winehq.org it's working.

I will try also native compilation.

Paul_

  • Full Member
  • ***
  • Posts: 106
Re: Game Contest 2018
« Reply #79 on: February 25, 2018, 11:33:05 pm »
I made progress in my game and I'm not sure about this :)

- game world is 2D grid
- entities (enemy soldier for example) are in separated list
- for collision calcualtions every 2DGrid.TCell is holding list of entities (if entity is in TCell dimensions then TCell.List is resized)

Code: Pascal  [Select]
  1.   TCell = record
  2.     List : Array of PEntity; // List of entites which are in TCell dimensions
  3.     Items : Integer;
  4.     ..
  5.   end;
  6.  
  7.  TGrid2D = record
  8.     List : Array of array of TCell;
  9.     Count : Integer;  
  10.     ..
  11.   end;  
  12.  
  13.   PEntity = ^TEntity;
  14.   TEntity = record
  15.     ID : Integer;
  16.     Param : TEntityParameters;
  17.    ..
  18.   end;
  19.  
  20.   TEntityManager = record
  21.     Count : Integer;
  22.     List : array of PEntity; // List of all entities
  23.     ..
  24.   end;
  25.  

Collisions (entity vs terrain, entity vs projectile, projectile vs terrain) are based on 2D grid and it's fast.
Problematic part - when is entity moving and it passes from one TCell to next one, TCell.List must be updated in current and in previous TCells.

Code: Pascal  [Select]
  1.   procedure Entity_AssignToCell( Entity : PEntity );
  2.   begin
  3.     With Grid2D.list[ Entity.CurCell.x, Entity.CurCell.y ] do begin
  4.       inc( Items );
  5.       Setlength( List, Items );
  6.       List[ Items - 1 ] := Entity;
  7.     end;
  8.   end;
  9.  
  10.   procedure Entity_RemoveFromCell( Entity : PEntity );
  11.     var i    : Integer;
  12.         item : Integer;
  13.   begin
  14.    // item := -1;
  15.     With Grid2D.list[ entity.prevCell.x, entity.prevCell.y ] do begin
  16.  
  17.     for i := 0 to items - 1 do
  18.       if List[i].ID = Entity.ID then item := i;
  19.  
  20.       // if ( item < 0 ) or ( item = items ) then exit;
  21.  
  22.        List[item] := nil;
  23.        For i := item to items - 2 do
  24.          List[i] := List[ i + 1 ];
  25.  
  26.        dec( Items );
  27.        SetLength( List, Items );
  28.      end;
  29.   end;

Detection area can be something like 1x3 TCell for soldiers, for vehicles 8x4. It means update of 3 x 300 TCell.list every frame.
Isn't this repeated setlength too costly? There is a better solution?
« Last Edit: February 26, 2018, 01:26:16 am by Paul_ »

lainz

  • Hero Member
  • *****
  • Posts: 2828
    • Home
Re: Game Contest 2018
« Reply #80 on: February 25, 2018, 11:49:19 pm »
For me is wrong.

The entity should have the position in a property.

You should iterate the entities and display in the correct cell.

Paul_

  • Full Member
  • ***
  • Posts: 106
Re: Game Contest 2018
« Reply #81 on: February 26, 2018, 12:07:19 am »
Iteration isn't good way if you have 1000 bullets and 1000 entities so it's 1 000 000 collision checks every frame.

In my implementation it's just 1000 checks (bullet vs TCell), it's something like spatial partition (https://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/).
Also I can get all needed objects on screen instead of iterate whole lists.

Problem is in dynamic array resizing (or not?). I'm not sure about this.
« Last Edit: February 26, 2018, 12:16:53 am by Paul_ »

lainz

  • Hero Member
  • *****
  • Posts: 2828
    • Home
Re: Game Contest 2018
« Reply #82 on: February 26, 2018, 12:17:17 am »
Iteration isn't good way if you have 1000 bullets and 1000 entities so it's 1 000 000 collision checks every frame.

In my implementation it's just 1000 checks, it's something like spatial partition (https://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/).
Also I can get all objects on screen instead of iterate whole lists.

Ok, I see.

Quote
Isn't this repeated setlength too costly? There is a better solution?

Well, try using FPObjectList / TFPList, I've used it recently instead of using Arrays.

The advantage is that is just a list of pointers as I can understand it, so it does not resize phisically the memory, just the list of pointers, and does it in an efficient way (doubling the memory and some kind of these tricks).

Paul_

  • Full Member
  • ***
  • Posts: 106
Re: Game Contest 2018
« Reply #83 on: February 26, 2018, 12:18:27 am »
Thanks, I will check it.

howardpc

  • Hero Member
  • *****
  • Posts: 2779
Re: Game Contest 2018
« Reply #84 on: February 26, 2018, 12:23:17 am »
The EntityManager would be faster if you used TfpList to hold pointers to all your entities, rather than using a dynamic array.
Then you also get a built-in Count and enumerator.

It might be that sorting the list by ID could help locating entities if you only need to move a few at once. Then you could use a binary search for location, rather than (possibly) enumerating the entire list to find a particular entity.
Sometimes the only way to know for sure if some adaptation would improve performance is simply to implement it and see if it makes a difference in the right direction.

Paul_

  • Full Member
  • ***
  • Posts: 106
Re: Game Contest 2018
« Reply #85 on: February 26, 2018, 01:37:30 am »
The EntityManager would be faster if you used TfpList to hold pointers to all your entities, rather than using a dynamic array.
..

EntityManager is list of pointers with memory allocation for records, it's probably done in similar way as TfpList.
I was more curious about TCell.List updates. Anyway, I must look at it and try more ways as you write.

howardpc

  • Hero Member
  • *****
  • Posts: 2779
Re: Game Contest 2018
« Reply #86 on: February 26, 2018, 10:51:34 am »
EntityManager is list of pointers with memory allocation for records, it's probably done in similar way as TfpList.

Implementing EntityManager as a dynamic array of pointers means you will spend time and resources reallocating and re-initialising the array with every SetLength required.
TFPList has a superior way of caching the underlying array of pointers, and if Capacity is set intelligently, it may not have to do any expensive memory reallocations at all.

Dynamic arrays have many advantages, including compiler management so no manual construction or destruction is needed, optimised enumeration with easy syntax and straightforward indexed  access to individual elements. But in situations where the array length changes frequently there is usually a performance degradation compared to some other more complex list implementations.

Paul_

  • Full Member
  • ***
  • Posts: 106
Re: Game Contest 2018
« Reply #87 on: February 26, 2018, 11:14:22 pm »
I tested TFPList bit. Access is almost same or only few % worse than old code, up to 10% worse in quicksort, really better when entities are removed. CPU load seems same but I have no proper tools to measure it.

This is the fastest way how access the elements in TFPList?

Code: Pascal  [Select]
  1. Type
  2.   PItem = ^TItem;
  3.   TItem = record
  4.     x, y : integer;
  5.     ..
  6.   end;
  7.  
  8. Var
  9.   _FPLManager : TFPList
  10.  
  11. Procedure Test;
  12.   var i : Integer;
  13. begin
  14.   for i := 0 to _FPLManager.Count - 1 do
  15.     // with TItem( _FPLManager[i]^ ) do    //slower
  16.     with TItem(_FPLManager.List[ i ]^) do  //better
  17.        y := y + 10;
  18. end;
  19.  
« Last Edit: February 27, 2018, 11:58:48 am by Paul_ »

howardpc

  • Hero Member
  • *****
  • Posts: 2779
Re: Game Contest 2018
« Reply #88 on: February 27, 2018, 09:58:25 am »
Code: Pascal  [Select]
  1. type
  2.   TItem = record
  3.     x, y: Integer;
  4.     ...
  5.   end;
  6.   PItem = ^TItem;
  7.  
  8. var
  9.   _FPLManager: TFPList; // list of PItem
  10.  
  11. procedure TestIncAllYBy(anIncValue: Integer);
  12. var
  13.   pi: PITem;
  14. begin
  15.   for pi in _FPLManager do
  16.     Inc(pi^.y, anIncValue);
  17. end;

Paul_

  • Full Member
  • ***
  • Posts: 106
Re: Game Contest 2018
« Reply #89 on: February 27, 2018, 12:19:46 pm »
Hm, it's slower:

Quote
// Your code
ACCESS - TEST: [1000 items]
TPFList:  0,0186982405558806 ms

ACCESS - TEST: [1000000 items]
TPFList:  29,1471465876548 ms

// My code
ACCESS - TEST: [1000 items]
TPFList:  0,00572563366190435 ms

ACCESS - TEST: [1000000 items]
TPFList:  19,3333494243441 ms

Full results: (Array vs Array of Pointers vs TFPList)
It needs some dynamic test also (add/remove), maybe later.

Code: Pascal  [Select]
  1.   PItem = ^TItem;
  2.   TItem = record
  3.     ID         : integer;
  4.     x, y       : integer;
  5.     Name       : String[80];
  6.     angle      : double;
  7.     alpha      : byte;
  8.     components : array [0..9] of integer;
  9.     p          : pointer;
  10.   end;
  11.  
  12.  
  13. ------- BENCHMARK WITH: [1000 items] ----------
  14. CREATE AND FILL - TEST: [1000 items]
  15. Array:    0,194234492909235 ms
  16. ArrayPtr: 0,331163778283136 ms
  17. TPFList:  0,291653345719301 ms
  18.  
  19. QUICKSORT - TEST: [1000 items]
  20. Array:    0,833338360105924 ms
  21. ArrayPtr: 0,0645437600661121 ms
  22. TPFList:  0,0687662490423998 ms
  23.  
  24. ACCESS - TEST: [1000 items]
  25. Array:    0,0138738923506596 ms
  26. ArrayPtr: 0,00482570168718595 ms
  27. TPFList:  0,0135722859952105 ms
  28.  
  29. FREE MEM - TEST: [1000 items]
  30. Array:    0,00482570168718595 ms
  31. ArrayPtr: 0,0226204766586842 ms
  32. TPFList:  0,0735919507295858 ms
  33.  
  34. End of benchmark.
  35.  
  36.  
  37. ------- BENCHMARK WITH: [10000 items] ----------
  38. CREATE AND FILL - TEST: [10000 items]
  39. Array:    0,497994190067783 ms
  40. ArrayPtr: 0,756012918979713 ms
  41. TPFList:  0,802323972886983 ms
  42.  
  43. QUICKSORT - TEST: [10000 items]
  44. Array:    2,47613777839259 ms
  45. ArrayPtr: 0,873294159394227 ms
  46. TPFList:  0,928626847179536 ms
  47.  
  48. ACCESS - TEST: [10000 items]
  49. Array:    0,0303728340560664 ms
  50. ArrayPtr: 0,039093746804838 ms
  51. TPFList:  0,0327786030902103 ms
  52.  
  53. FREE MEM - TEST: [10000 items]
  54. Array:    0,0448074482609297 ms
  55. ArrayPtr: 0,826983105486958 ms
  56. TPFList:  0,673314608431018 ms
  57.  
  58. End of benchmark.
  59.  
  60.  
  61. ------- BENCHMARK WITH: [50000 items] ----------
  62. CREATE AND FILL - TEST: [50000 items]
  63. Array:    10,8603071577652 ms
  64. ArrayPtr: 7,40538551556901 ms
  65. TPFList:  6,97137135204913 ms
  66.  
  67. QUICKSORT - TEST: [50000 items]
  68. Array:    21,7052322986162 ms
  69. ArrayPtr: 6,7137979707802 ms
  70. TPFList:  5,92750545910796 ms
  71.  
  72. ACCESS - TEST: [50000 items]
  73. Array:    0,645139885871467 ms
  74. ArrayPtr: 0,644536669521891 ms
  75. TPFList:  0,655997780163834 ms
  76.  
  77. FREE MEM - TEST: [50000 items]
  78. Array:    1,05623182810747 ms
  79. ArrayPtr: 6,7563247234253 ms
  80. TPFList:  5,35143384526294 ms
  81.  
  82. End of benchmark.
  83.  
  84.  
  85. ------- BENCHMARK WITH: [100000 items] ----------
  86. CREATE AND FILL - TEST: [100000 items]
  87. Array:    21,0872009428758 ms
  88. ArrayPtr: 12,4165413216539 ms
  89. TPFList:  10,7357626653725 ms
  90.  
  91. QUICKSORT - TEST: [100000 items]
  92. Array:    32,6069853595016 ms
  93. ArrayPtr: 14,6100539259867 ms
  94. TPFList:  14,8843560381129 ms
  95.  
  96. ACCESS - TEST: [100000 items]
  97. Array:    1,30579862607799 ms
  98. ArrayPtr: 1,65425273774608 ms
  99. TPFList:  1,67294145307776 ms
  100.  
  101. FREE MEM - TEST: [100000 items]
  102. Array:    2,1742210272162 ms
  103. ArrayPtr: 13,5324384854906 ms
  104. TPFList:  13,8579838493328 ms
  105.  
  106. End of benchmark.
  107.  
  108.  
  109. ------- BENCHMARK WITH: [1000000 items] ----------
  110. CREATE AND FILL - TEST: [1000000 items]
  111. Array:    60,415382811725 ms
  112. ArrayPtr: 63,9610770252843 ms
  113. TPFList:  62,4727572244083 ms
  114.  
  115. QUICKSORT - TEST: [1000000 items]
  116. Array:    407,911151726854 ms
  117. ArrayPtr: 229,015171783549 ms
  118. TPFList:  239,287614569962 ms
  119.  
  120. ACCESS - TEST: [1000000 items]
  121. Array:    15,8138863754558 ms
  122. ArrayPtr: 19,8080906158596 ms
  123. TPFList:  19,2973543319395 ms
  124.  
  125. FREE MEM - TEST: [1000000 items]
  126. Array:    22,1558542282291 ms
  127. ArrayPtr: 186,838695713603 ms
  128. TPFList:  184,151844091662 ms
  129.  
  130. End of benchmark.
  131.  
« Last Edit: February 27, 2018, 12:24:55 pm by Paul_ »

 

Recent

Get Lazarus at SourceForge.net. Fast, secure and Free Open Source software downloads Open Hub project report for Lazarus