Best way to delete an instance of a game object

[Tomi]

Hello everybody!

I would like delete those instances in my game, which are no longer necessary.
The logic in my program is the following:
When I create an instance of an object, I set its variable named 'exists' to true and when this instance become unnecessary, I set it to false. Finally, I check whether it should be delete.
To delete I used the FreeAndNil() function, but this threw an error in an Assembly window. So, instead of that, now I use the function Delete() in this mode:

Code: Pascal  [Select][+][-]

1. if numberofunits>0 then
2.  begin
3.    for i:=0 to numberofunits-1 do
4.    begin
5.       if gameunits[i].exists=false then
6.       begin
7.            delete(gameunits,i,1);
8.            dec(numberofunits,1);
9.       end
10.       else
11. (...)

These instances are in a dynamic array. Now, there is no errors yet, but I don't know what will be if I set an instance to another to target?
Because in this case if this array is rearranged, the instance will pursue a wrong target, maybe a friendly one instead of enemies.
Let me show it you more precisely:
I choose for example the first instance in the array to target for the player. This is the index 0. But when the array is rearranged because we remove an element of it, the following indexes will shift to left and overwrite the 0. with its own datas and so on.
Finally, the target will be a totally different instance.
So, how can I delete instances from dynamic array to prevent this mixing? Maybe FreeAndNil(gameunits) would be good for this? But why cause error when an instance destroyed?

[Handoko]

Try this:

Code: Pascal  [Select][+][-]

1. unit Unit1;
2.  
3. {$mode objfpc}{$H+}
4.  
5. interface
6.  
7. uses
8.   Classes, SysUtils, Forms, Controls, Graphics, Dialogs, ExtCtrls, StdCtrls;
9.  
10. type
11.  
12.   TItem = record
13.     Item:    TShape;
14.     Useless: Boolean;
15.   end;
16.  
17.   { TForm1 }
18.  
19.   TForm1 = class(TForm)
20.     Button1: TButton;
21.     procedure Button1Click(Sender: TObject);
22.     procedure FormCreate(Sender: TObject);
23.     procedure ItemMouseDown(Sender: TObject; Button: TMouseButton;
24.       Shift: TShiftState; X, Y: Integer);
25.   private
26.     Items: array of TItem;
27.     procedure MarkRemove(Item: TShape);
28.     procedure DoRemove;
29.   end;
30.  
31. var
32.   Form1: TForm1;
33.  
34. implementation
35.  
36. {$R *.lfm}
37.  
38. { TForm1 }
39.  
40. procedure TForm1.FormCreate(Sender: TObject);
41. var
42.   Item: TShape;
43.   i:    Integer;
44. begin
45.   Width           := 520;
46.   Caption         := 'Please click some squares';
47.   Button1.Visible := False;
48.   SetLength(Items, 5);
49.   for i := 0 to Length(Items)-1 do
50.   begin
51.     Item              := TShape.Create(nil);
52.     Item.Parent       := Self;
53.     Item.Left         := 60 + i*80;
54.     Item.Top          := 50;
55.     Item.Brush.Color  := Random($FFFF);
56.     Item.OnMouseDown  := @ItemMouseDown;
57.     Items[i].Item     := Item;
58.     Items[i].Useless  := False;
59.   end;
60. end;
61.  
62. procedure TForm1.Button1Click(Sender: TObject);
63. begin
64.   DoRemove;
65.   Caption := 'Please click some squares';
66. end;
67.  
68. procedure TForm1.ItemMouseDown(Sender: TObject; Button: TMouseButton;
69.   Shift: TShiftState; X, Y: Integer);
70. const
71.   SelectedCount: Integer = 0;
72. begin
73.   if not(Sender is TShape) then Exit;
74.   MarkRemove(Sender as TShape);
75.   (Sender as TShape).Brush.Color := clWhite;
76.   Inc(SelectedCount);
77.   if SelectedCount < 2 then Exit;
78.   Caption         := 'Click the button to remove all white squares' ;
79.   Button1.Visible := True;
80. end;
81.  
82. procedure TForm1.MarkRemove(Item: TShape);
83. var
84.   i: Integer;
85. begin
86.   if not(Item is TShape) then Exit;
87.   for i := 0 to Length(Items)-1 do
88.     if Items[i].Item = Item then
89.       Items[i].Useless := True;
90. end;
91.  
92. procedure TForm1.DoRemove;
93. var
94.   RemovedCount: Integer;
95.   IndexStart, IndexEnd: Integer;
96.   i, j: Integer;
97. begin
98.   RemovedCount := 0;
99.   for i := 0 to Length(Items)-1 do
100.   begin
101.     if Items[i].Useless then
102.       begin
103.         Items[i].Item.Free;
104.         Inc(RemovedCount);
105.         Continue;
106.       end;
107.     if RemovedCount > 0 then
108.       Items[i-RemovedCount] := Items[i];
109.   end;
110.   SetLength(Items, Length(Items)-RemovedCount);
111. end;
112.  
113. end.

~edit~
The variables IndexStart, IndexEnd, J in line #95 and #96  are not needed. I forgot to remove them.

[Tomi]

Thanks, Handoko, for your example code! So, you use Free and SetLength() in your code.
Meanwhile I figured out a trick: what if I would add a unique number for all instances? Like this:
Instance 0. - id:=0;
Instance 1. - id:=1;
(...)
Instance n. - id:=n;
And when this array rearranged, the index changes but the id remains the same. I'm just worried that in this case more difficult follow and handle the instances, because a for loop is not enough, but I also need check the id, besides the number of id's will constantly increasing.

[Bart]

A bit unrelated, but please don't do

Code: Pascal  [Select][+][-]

1.   if Condition=False then ...

But do

Code: Pascal  [Select][+][-]

1.   if not Condition then ...

There is no ndeed to compare a boolean variable (or function result) to either True or False.
If that would be needed then, since the expression (Condition = False) itself is a boolean expression, you would have to do (to stay consistent)

Code: Pascal  [Select][+][-]

1.   if ((((((((((((((Condition = False) = True) = True) = True) {etc. at infinitum}))))))))))

Bart

[Чебурашка]

Hello everybody!

I would like delete those instances in my game, which are no longer necessary.
The logic in my program is the following:
When I create an instance of an object, I set its variable named 'exists' to true and when this instance become unnecessary, I set it to false. Finally, I check whether it should be delete.
To delete I used the FreeAndNil() function, but this threw an error in an Assembly window. So, instead of that, now I use the function Delete() in this mode:

Code: Pascal  [Select][+][-]

1. if numberofunits>0 then
2.  begin
3.    for i:=0 to numberofunits-1 do
4.    begin
5.       if gameunits[i].exists=false then
6.       begin
7.            delete(gameunits,i,1);
8.            dec(numberofunits,1);
9.       end
10.       else
11. (...)

These instances are in a dynamic array. Now, there is no errors yet, but I don't know what will be if I set an instance to another to target?
Because in this case if this array is rearranged, the instance will pursue a wrong target, maybe a friendly one instead of enemies.
Let me show it you more precisely:
I choose for example the first instance in the array to target for the player. This is the index 0. But when the array is rearranged because we remove an element of it, the following indexes will shift to left and overwrite the 0. with its own datas and so on.
Finally, the target will be a totally different instance.
So, how can I delete instances from dynamic array to prevent this mixing? Maybe FreeAndNil(gameunits) would be good for this? But why cause error when an instance destroyed?

One useful trick when you deal with variable arrays(*) or lists, and you scan them to selectively delete their contents, is to scan them in reverse mode.

Code: Pascal  [Select][+][-]

1. // assuming it goes from 0 to (numberofelements - 1)
2. for i = numberofelements - 1 downto 0
3.  

in this way, when you delete an element, the following ones will move one position back (*) but this doesn't affect your process. If you scan it forward, in case of delete you have to prevent i to do +1 otherwise you miss the item after the deleted one (this is why to scan forward is better to use a loop instead like while, repeat, even goto + label if you are braveheart).


* = in arrays when you delete an element you have to take care of moving backwards all subsequent elements, in lists this is done for you...

[Handoko]

what if I would add a unique number for all instances?

Done!
Tested on Linux GTK2 only, it may behave or look different on Windows:

Code: Pascal  [Select][+][-]

1. unit Unit1;
2.  
3. {$mode objfpc}{$H+}
4.  
5. interface
6.  
7. uses
8.   Classes, SysUtils, Forms, Controls, Graphics, Dialogs, StdCtrls, Menus,
9.   Buttons;
10.  
11. type
12.  
13.   TItem = record
14.     ID:     Integer;
15.     Unused: Boolean;
16.     Box:    TEdit;
17.   end;
18.  
19.   { TForm1 }
20.  
21.   TForm1 = class(TForm)
22.     btnGenerate: TButton;
23.     btnSelect: TButton;
24.     btnRemove: TButton;
25.     lblInfo: TLabel;
26.     PopupMenu1: TPopupMenu;
27.     procedure btnGenerateClick(Sender: TObject);
28.     procedure btnSelectClick(Sender: TObject);
29.     procedure btnRemoveClick(Sender: TObject);
30.     procedure BoxClick(Sender: TObject);
31.     procedure BoxEnter(Sender: TObject);
32.     procedure FormCreate(Sender: TObject);
33.     procedure MenuItemClick(Sender: TObject);
34.   private
35.     MenuResult: Integer;
36.     Items: array of TItem;
37.     procedure AddItem;
38.     procedure SelectItem(ID: Integer);
39.     procedure SelectItem(Box: TEdit);
40.     procedure RemoveSelected;
41.   end;
42.  
43. const
44.   BoxSize = 30;
45.  
46. var
47.   Form1: TForm1;
48.  
49. implementation
50.  
51. {$R *.lfm}
52.  
53. { TForm1 }
54.  
55. procedure TForm1.btnGenerateClick(Sender: TObject);
56. var
57.   MenuItem: TMenuItem;
58.   i: Integer;
59. begin
60.  
61.   if Length(Items) > 20 then
62.   begin
63.     ShowMessage('You have reached the maximum item count.');
64.     Exit;
65.   end;
66.  
67.   PopupMenu1.Items.Clear;
68.   for i := 0 to 2 do
69.   begin
70.     MenuItem := TMenuItem.Create(PopupMenu1);
71.     case i of
72.       0: MenuItem.Caption := '1 item';
73.       1: MenuItem.Caption := '3 items';
74.       2: MenuItem.Caption := 'Cancel';
75.     end;
76.     MenuItem.Tag     := i;
77.     MenuItem.OnClick := @MenuItemClick;
78.     PopupMenu1.Items.Add(MenuItem);
79.   end;
80.  
81.   MenuResult := 0;
82.   PopupMenu1.PopUp(Mouse.CursorPos.X, Mouse.CursorPos.Y);
83.   case MenuResult of
84.     0: AddItem;
85.     1: for i := 0 to 2 do AddItem;
86.   end;
87.  
88.   if Length(Items) > 0 then
89.   begin
90.     Caption           := 'Now select some items';
91.     lblInfo.Visible   := True;
92.     btnSelect.Enabled := True;
93.   end;
94.  
95. end;
96.  
97. procedure TForm1.btnSelectClick(Sender: TObject);
98. var
99.   MenuItem: TMenuItem;
100.   ID, i     : Integer;
101. begin
102.  
103.   if Length(Items) <= 0 then
104.   begin
105.     ShowMessage('Please click the Generate button.');
106.     Exit;
107.   end;
108.  
109.   PopupMenu1.Items.Clear;
110.   for i := 0 to Length(Items)-1 do
111.     if not(Items[i].Unused) then
112.     begin
113.       ID := Items[i].ID;
114.       MenuItem := TMenuItem.Create(PopupMenu1);
115.       MenuItem.Caption := 'Item no. ' + ID.ToString;
116.       MenuItem.Tag     := ID;
117.       MenuItem.OnClick := @MenuItemClick;
118.       PopupMenu1.Items.Add(MenuItem);
119.     end;
120.  
121.   MenuResult := 0;
122.   PopupMenu1.PopUp(Mouse.CursorPos.X, Mouse.CursorPos.Y);
123.   SelectItem(MenuResult);
124.  
125. end;
126.  
127. procedure TForm1.btnRemoveClick(Sender: TObject);
128. begin
129.   RemoveSelected;
130.   if Length(Items) <= 0 then
131.   begin
132.     Caption           := 'Please generate some boxes';
133.     lblInfo.Visible   := False;
134.     btnSelect.Enabled := False;
135.   end;
136. end;
137.  
138. procedure TForm1.BoxClick(Sender: TObject);
139. begin
140.   if not(Sender is TEdit) then Exit;
141.   SelectItem(Sender as TEdit);
142. end;
143.  
144. procedure TForm1.BoxEnter(Sender: TObject);
145. begin
146.   SelectNext(Sender as TEdit, True, True); // Remove focus
147. end;
148.  
149. procedure TForm1.FormCreate(Sender: TObject);
150. begin
151.   Caption               := 'Please generate some boxes';
152.   Constraints.MinWidth  := 320;
153.   Constraints.MinHeight := 240;
154.   lblInfo.Caption       := 'You can select an item by clicking on it.';
155.   lblInfo.Visible       := False;
156.   btnSelect.Enabled     := False;
157.   btnRemove.Enabled     := False;
158. end;
159.  
160. procedure TForm1.MenuItemClick(Sender: TObject);
161. begin
162.   if not(Sender is TMenuItem) then Exit;
163.   MenuResult := (Sender as TMenuItem).Tag;
164. end;
165.  
166. procedure TForm1.AddItem;
167. var
168.   NewBox:   TEdit;
169.   X, Y, ID: Integer;
170.   i:        Integer;
171.   Found:    Boolean;
172. begin
173.  
174.   // Prevent overlap
175.   repeat
176.     X := Random(Width - BoxSize);
177.     Y := Random(Height - BoxSize -60);
178.     Found := False;
179.     for i := 0 to Length(Items)-1 do
180.       if Abs(X-Items[i].Box.Left) < BoxSize then
181.         if Abs(Y-Items[i].Box.Top) < BoxSize then
182.         begin
183.           Found := True;
184.           Break;
185.         end;
186.   until not(Found);
187.  
188.   // Get an ID
189.   ID := 0;
190.   repeat
191.     Found := False;
192.     for i := 0 to Length(Items)-1 do
193.       if Items[i].ID = ID then
194.       begin
195.         Found := True;
196.         Inc(ID);
197.         Break;
198.       end;
199.   until not(Found);
200.  
201.   NewBox          := TEdit.Create(Self);
202.   NewBox.OnClick  := @BoxClick;
203.   NewBox.OnEnter  := @BoxEnter;
204.   NewBox.ReadOnly := True;
205.   NewBox.TabStop  := False;
206.   NewBox.Caption  := ID.ToString;
207.   NewBox.Color    := Random($FFFF);
208.   NewBox.Left     := X;
209.   NewBox.Top      := Y;
210.   NewBox.Width    := BoxSize;
211.   NewBox.Height   := BoxSize;
212.   NewBox.Parent   := Self;
213.   i := Length(Items);
214.   SetLength(Items, i+1);
215.   Items[i].ID     := ID;
216.   Items[i].Box    := NewBox;
217.   Items[i].Unused := False;
218.  
219. end;
220.  
221. procedure TForm1.SelectItem(ID: Integer);
222. var
223.   i: Integer;
224. begin
225.   for i := 0 to Length(Items)-1 do
226.     if Items[i].ID = ID then
227.     begin
228.       Items[i].Box.Color := clWhite;
229.       Items[i].Unused    := True;
230.     end;
231.   btnRemove.Enabled := True;
232. end;
233.  
234. procedure TForm1.SelectItem(Box: TEdit);
235. var
236.   i: Integer;
237. begin
238.   for i := 0 to Length(Items)-1 do
239.     if Items[i].Box = Box then
240.     begin
241.       Items[i].Box.Color := clWhite;
242.       Items[i].Unused := True;
243.     end;
244.   btnRemove.Enabled := True;
245. end;
246.  
247. procedure TForm1.RemoveSelected;
248. var
249.   RemovedCount: Integer;
250.   i: Integer;
251. begin
252.  
253.   RemovedCount := 0;
254.   for i := 0 to Length(Items)-1 do
255.   begin
256.     if Items[i].Unused then
257.       begin
258.         Items[i].Box.Free;
259.         Inc(RemovedCount);
260.         Continue;
261.       end;
262.     if RemovedCount > 0 then
263.       Items[i-RemovedCount] := Items[i];
264.   end;
265.   SetLength(Items, Length(Items)-RemovedCount);
266.   btnRemove.Enabled := False;
267. end;
268.  
269. end.

So, you use Free and SetLength() in your code.

If you want to use Delete, read Чебурашка's reply #4.

Instead of using Delete, I use SetLength for better performance. For example if there are hundreds of items are marked to be deleted, array rearrangement only needed to perform once. Of course in this small example, the performance gain is unnoticeable.

Using FreeAndNil or Free only is more about personal preference. I see no reason to use FreeAndNil for the code.

Also, read Bart's advise in the reply #3.

[Tomi]

Oh, thank you all your answers! I try to use everything from your advices in my program.

[flowCRANE]

What's the point of flagging an object and deleting it later when you can delete it right away when logic decides it's no longer needed?

[Seenkao]

What's the point of flagging an object and deleting it later when you can delete it right away when logic decides it's no longer needed?

Если объект помечен как удалённый, его место мы можем использовать под другой объект. И нам не надо производить лишних действий во время игры. Это очень эффективно для небольших программ, которые не потребляют много памяти. Но может быть критично для огромных программ.
Google translate:
If an object is marked as deleted, we can use its place for another object. And we don't need to make extra actions during the game. This is very efficient for small programs that don't consume a lot of memory. But it can be critical for huge programs.

[flowCRANE]

If an object is marked as deleted, we can use its place for another object.

And? You can do this without marking the object as deleted, and just free it right away.

I use such a method myself, but I use my own list implementation, which is adapted to quickly manage items (regardless of what type of data it stores). An efficient method of deleting list items is to move the last item of the list to the one being removed (complexity O(1) for each deletion).

And we don't need to make extra actions during the game.

You're contradicting yourself, what you write is illogical.

The quickest solution is to determine whether an object is needed and if not, remove it from the list immediately (if the order of objects in the list does not matter, delete the object from the list without relocation of its internal data block). If an object is marked for deletion, then it has to be found and deleted later, which requires additional CPU time and therefore reduces performance, which is critical in large productions.

So, if you want the best performance, you should delete objects immediately and in such a way as to minimize the demand for CPU time (as described above).

[Seenkao]

Нет, я не противоречу сам себе.
Первое что надо понимать, это то, что мы воспринимаем информацию по разному.
Второе - мы думаем по разному. 

Да, достаточно пометить объект как удалённый и если объект удалён, не использовать его больше.
На каждый объект выделяется память. Если объекты одинаковые, то указывая что объект удалён, мы можем из списка удалённых объектов его вытащить и перезаписать данные для нового объекта.
При таких действиях не надо чистить память и выделять её заново. Во время игрового процесса, это может быть критичным. Но конечно же не для лёгких приложений.

Google translate:
No, I'm not contradicting myself.
The first thing to understand is that we perceive information in different ways.
Second, we think differently.

Yes, it's enough to mark an object as deleted, and if the object is deleted, don't use it anymore.
Memory is allocated for each object. If the objects are the same, then indicating that the object is deleted, we can pull it out of the list of deleted objects and overwrite the data for the new object.
With such actions, it is not necessary to clean the memory and allocate it again. During gameplay, this can be critical. But certainly not for light applications.

Я даже не уверен, что google translate меня верно перевёл. 

[flowCRANE]

This would be a good solution only if the object is always represented in the same way, i.e. if each object, regardless of type, consisted of the same data and always took up the same amount of memory. Although this would be good up to a point, because in order to use the deleted object's memory, you first need to know where the deleted object is in the list, and that requires a buffer search, which takes up CPU time.

That's why I don't like this idea. If the objects in the list do not need to be sorted (their order does not have to be preserved after deleting a given object), it is much better to remove the object by overwriting it with the data of the last object in the list. This does not require any allocations, especially since lists are always allocated with spare space (Capacity is usually greater than Count). This is especially important if the list holds pointers/references.

[Seenkao]

Если сортировать объекты не обязательно, то достаточно легко решаемо. И, данный метод, хорошую эффективность может показать при достаточно большом количестве объектов.

Ну и да, одинаково объявленных объектов. Нам можно просто содержать второй список, список удалённых объектов и их номера.

Но большинству людей лучше это делать не стоит! При неправильном решении это может отнять очень много рабочего времени процессора!

Потому, по большей части, ты прав! 

Google translate:
If it is not necessary to sort objects, then it is quite easy to solve. And, this method can show good efficiency with a sufficiently large number of objects.

Well and yes, equally declared objects. We can just keep the second list, the list of removed objects and their numbers.

But most people shouldn't do it! With the wrong decision, this can take a lot of CPU time!

Because, for the most part, you're right!

[Tomi]

Hello everybody!

The new question here is: Best place to delete an instance of a game object.
Because as I can see, the problem with delete occurs because the game logic in main refresh loop is wrong. So, this loop happening in every 25 fps:

Code: Pascal  [Select][+][-]

1. procedure TForm1.screenrefreshing(Sender: TObject);
2. begin
3. If not exists then FreeAndNil else we work with it.
4. (...)
5. with canvas do invalidate;
6. end;

But it is not good and I don't know, where can I place the removing of instances? Because now the FreeAndNil and Invalidate(?) are get stuck and occur an error.

[Handoko]

What I like about programming is, there is always more than 1 way to do the same thing.

It depends of what kind of the game you're developing but basically The flow should be something like this:

Code: Pascal  [Select][+][-]

1. Initialization
2. Start of Game Loop
3.    Check user input
4.    Check collision
5.    Update object state
6.    Render screen
7. Goto #2
8. Shutdown

You can delete the object immediately if it is no longer needed, for example Object.Health < 1 (after it's hit by player weapon or projectile) in the collision detection procedure/subroutine/block which is in step #4 above.

But if it is a side scrolling shooting game, you may do that this way:

Code: Pascal  [Select][+][-]

1. Initialization
2. Start of Game Loop
3.    Check user input
4.    Check collision
5.    Check objects out of screen
6.    Update object state
7.    Remove unused objects
8.    Render screen
9. Goto #2
10. Shutdown

You can remove the unused objects in the step #7. Marking object as unused can be done in step #4 and #5. Maybe for performance reason, because you remove all the unused objects in just 1 pass, see my previous post. Or maybe any other reasons, for example after health <= 0, it shouldn't be removed immediately because you want to show some explosion animations, etc.