www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Optimization when using a 2-dimensional array of objects

reply Liam McGillivray <yoshi.pit.link.mario gmail.com> writes:
In the [game I am currently 
making](https://github.com/LiamM32/Open_Emblem/blob/master/oe-r
ylib/source/app.d), I have a `Map` class (actually a combination of an
interface & class template, but I'll call it a "class" for simplicity), in
which there will probably be only one instance running at a time. In that map
class is a 2-dimensional dynamic array of `Tile` objects called `grid`. What
these `Tile` objects represent are like squares on a chessboard. Their
placement in `grid` represents their location on the map.

Whenever a function in the game has to pass a location on the 
map, I have a dilemma between passing a reference to the tile 
object, and passing it's grid coordinates through `struct 
Vector2i {int x; int y;}`. The functions that receive this 
information sometimes must access the Tile's variables to know 
it's properties, but may also need to know it's location so that 
it can find neighbouring tiles. The `Unit` class also has a 
2-dimensional dynamic array of entities holding information on 
the unit's distance from that tile, and whether it can reach it 
during this turn.

Is one option more efficient than the other? I already have the 
location of each tile cached as a pair of variables within each 
tile. To get a location from a Tile object, a call would be made 
to the member function `Vector2i location()`. To get a tile 
object from it's coordinates, a member function of `Map` `Tile 
getTile(Vector2i location)` would be called. Should I stick to 
one over the other?

Is there a memory allocation technique that would make each 
tile's location in `grid` inferrable based on it's memory 
address? It would be nice if the two were interchangeable, so 
that I wouldn't have this dilemma.

Not knowing which option is best has lead to a little bit of 
messy syntax. Right now I have multiple versions of the functions 
`getReachable` & `getAttackable` in the 
[`Unit`](https://github.com/LiamM32/Open_Emblem/blob/master/source/unit.d)
class which return a different type, because I'm not sure which is better.
Mar 21
parent reply monkyyy <crazymonkyyy gmail.com> writes:
On Friday, 22 March 2024 at 02:19:07 UTC, Liam McGillivray wrote:

 In the [game I am currently 
 making](https://github.com/LiamM32/Open_Emblem/blob/master/oe-r
ylib/source/app.d), I have a `Map` class (actually a combination of an
interface & class template, but I'll call it a "class" for simplicity), in
which there will probably be only one instance running at a time. In that map
class is a 2-dimensional dynamic array of `Tile` objects called `grid`. What
these `Tile` objects represent are like squares on a chessboard. Their
placement in `grid` represents their location on the map.


```d
enum tile{wall,field....}
bool ispassable(tile t)=>...
alias grid_=tile[maxhieght][maxwidth];
grid_ grid;
```
your not simplifying anything here with all them oo terms



 Is one option more efficient than the other?


You should probaly do the lazyest thing, factor out your 
"ispassable" logic, like what your walking n of 3, n of 8, n of 
15? so long as you dont do something insane it will be fast on a 
modern computer; allocating several dynamic array that are the 
size of your game world every frame could easily be not very sane.

and if you really really wanted to care, you could precompute the 
"connected compoints" by flood filling across passable tiles with 
a "color" of 0, then finding an empty cell, flood filling with 1, 
etc.; and when you draw the overlay for where you can move you 
can do a heuristic check for a) they are in the same component, 
and b) the manhattan distances before c) doing a greedy check


 Is there a memory allocation technique that would make each 
 tile's location in grid inferrable based on it's memory address?


Yes its called an array
theres some details you need to know and you need to cast 
pointers; just try some trial and error with code like:

```d
int[10] foo;
&foo.print;
&foo[1].print;
(&foo[7]-&foo[0]).print;
```
with whatever casts you need to make it just work
Mar 22
parent Liam McGillivray <yoshi.pit.link.mario gmail.com> writes:
On Friday, 22 March 2024 at 07:34:33 UTC, monkyyy wrote:

 Is one option more efficient than the other?


 You should probaly do the lazyest thing, factor out your 
 "ispassable" logic, like what your walking n of 3, n of 8, n of 
 15? so long as you dont do something insane it will be fast on 
 a modern computer; allocating several dynamic array that are 
 the size of your game world every frame could easily be not 
 very sane.


Well, none of the stuff you wrote closely resembles the code that 
I have.

There are 3 reasons why I put this kind of effort into 
optimization:
- I'm obsessive.
- For the learning experience.
- Because things may get more demanding when I get further with 
the enemy AI system. One possibility is to have it make multiple 
copies of all the game objects which it will use to look ahead to 
the next 1-2 turns.


 and if you really really wanted to care, you could precompute 
 the "connected compoints" by flood filling across passable 
 tiles with a "color" of 0, then finding an empty cell, flood 
 filling with 1, etc.; and when you draw the overlay for where 
 you can move you can do a heuristic check for a) they are in 
 the same component, and b) the manhattan distances before c) 
 doing a greedy check


I barely understand any of this, though I know what a Manhattan 
distance is. Is this about measuring distances? Manhattan 
distances appear to be how distances are determined in Fire 
Emblem, though I'm using a slightly more intensive `abs(x) + 
abs(y) + max(abs(x) + abs(y))` whenever I need a quick estimate 
of distance that doesn't account for obstructions.


 Is there a memory allocation technique that would make each 
 tile's location in grid inferrable based on it's memory 
 address?


 Yes its called an array
 theres some details you need to know and you need to cast 
 pointers; just try some trial and error with code like:


But objects are reference by default. This means that they don't 
really 'live' in the array I put them in, doesn't it? Wouldn't 
the the array entries just be references on the same level as any 
other?


 ```d
 int[10] foo;
 &foo.print;
 &foo[1].print;
 (&foo[7]-&foo[0]).print;
 ```


This appears to be a different programming language. It isn't D.
Mar 22