[ / / / / / / / / / / / / / ] [ dir / 1970floe / aov / caraota / cyoa / firechan / just / marx / o ][Options][ watchlist ]

/tech/ - Technology

You can now write text to your AI-generated image at https://aiproto.com It is currently free to use for Proto members.
Email
Comment *
File
Select/drop/paste files here
Password (Randomized for file and post deletion; you may also set your own.)
* = required field[▶ Show post options & limits]
Confused? See the FAQ.
Expand all images

File (hide): 406c2937e494e72⋯.png (13.71 KB, 400x414, 200:207, c.png) (h) (u)

[–]

 No.973839>>973846 >>973847 >>973857 >>973877 >>973914 >>973943 >>974562 >>974563 [Watch Thread][Show All Posts]

As one of my beginner C projects I'm making a simulation of a few animals. If an animal doesn't manage to get to any food within a certain amount of time, it will die.

In each frame of the game, a linked list containing pointers to these animals is traversed. First, the creatures hunger is checked, If it is too hungry, it will be removed from the list. I decided to use a linked list to store the pointers to the animals. I chose a linked list because I'm under the impression it should be pretty quick to drop an animal from it, if I'm already in that area of the list.

After the hunger check is complete, I'm planning to draw them. I have two ideas about how to do this:

A) Every animal that lives has it's location stored in an array, so I can quickly go through them and draw them (a this stage, it doesn't matter about deleting animals, they've all survived this frame, so an array should be okay?)

B) Just loop through the linked list again, drawing them.

I have a feeling option A may be faster (less dereferencing of pointers, plus the pointers to the animals will all be in continuous memory because of the array), but I'm not 100% sure. Should I just loop through the linked list to keep things simple? Or is this design just flat out retarded?

I've Google'd a lot about this, but it's not a question that is easily put into search terms. I have only been programming in C for around two weeks so please be kind.

 No.973846>>973871

>>973839 (OP)

Why can't you draw your animals during first traversal?

Why do you even bother with optimisation at this stage?


 No.973847

>>973839 (OP)

>>Every animal that lives has it's location stored in an array,

Sorry, to make clear, I mean it's memory location, not location on the screen.


 No.973857

>>973839 (OP)

use ncurses.

draw the animals when they survive as you're going through the linked list.

after you've gone through the linked list, update the screen.

ncurses will take care of updating it optimally. there won't be anything absurd like animal #1 being drawn, then your program going through the list for a bit, then animal #2 being drawn.


 No.973871

>>973846

I was worried about optimization as I'm planning to eventually have a few hundred of them running around. Maybe right now isn't the time though. (You) and >>973857's answer makes complete sense. I was clearly over-thinking things. Thanks you.


 No.973877>>973880

>>973839 (OP)

How many genders of animals are there?


 No.973880>>973915

>>973877

Frig off Coraline


 No.973914

>>973839 (OP)

Just keep animals in an array, ignore/overwrite the dead. Linked lists are just more code to write that's also slower, and for what?


 No.973915>>973934 >>974244

>>973880

His name is Corey.


 No.973934>>973954

>>973915

Excuse me honey, you meant her.


 No.973938>>973946 >>974244

So they're living in a 2D array or something? And they do a random walk to find food and die if they don't find it quick enough?

Anyway you can probably just use an array of pointer to animal structs, and then null the ones that die (and maybe even free that struct memory). Then you just traverse the array, skipping all nulls. Probably also keep a counter too, so you don't end up in an endless loop if they all die.


 No.973943

>>973839 (OP)

Linked list vs array only really matters when order is relevant. Based on your description you have an unordered set of animals, so you can do constant time removals/insertion in both linked lists and arrays. In that case, array is usually preferable, for speed and simplicity purposes. The main problem with arrays is the fear of a realloc if you run out of space.


 No.973946

>>973938

If you aren't working in parallel and don't care for order you can just do nigger[i] = nigger[--niggercount]


 No.973954>>973965


 No.973965>>973979

>>973954

Xir's being sarcastic anon.


 No.973979

>>973965

>spoiler

Actually spilled my coffee, I was not expecting that.


 No.974128>>974244 >>974575

>linked list

STOP

Linked list is never the right choice.


 No.974209

ITT: C niggers show again why C programmers are superior to other programmers.


 No.974244>>974252 >>974307 >>974357

File (hide): d82b879aaa626fb⋯.jpg (44.05 KB, 720x540, 4:3, bnU9690.jpg) (h) (u)

>>973915

Fuck off Corey

>>973938

>>974128

I am planning to add the ability for the animals to split into two if they've eaten an extra amount of food, meaning the simulation could run for 1000s and 1000s of cycles.

Wouldn't I end up with a lot of redudant space in the array after cycling life/death for a while using an array?


 No.974252>>974257

>>974244

You will learn a lot more writing test cases, than arguing on /tech/.


 No.974257

>>974252

Hey I'm not arguing at all. Like I said I've only been writing this stuff for 2 weeks, so in no way do I think my solution is right. It wasn't a rhetorical question, I am genuinely curious.


 No.974307

>>974244

Re-organizing arrays and/or having redundant space in it is a lot faster than having to loop through a linked list.

For a test case it's not a big deal, but for future's sake it's better to practice using arrays.


 No.974329>>974417 >>974444

Linked list are almost always for university intellectuals who can't understand the cost of pointer dereferencing and lack of data locality or just ignore it because "muh CY hardware".


 No.974357>>974367

>>974244

keep your animals in an array shaped like the physical space that they're in

bonus: you don't have to care about population

malus: you'll skip a lot of empty space when handling a few animals

if animals can't coexist with food or terrain features, you can put them all in the same array.


 No.974367>>974398 >>974905

>>974357

Even better, use quadtrees to store your animals and other things. This way you can easily calculate potential collisions between animals. It also gives you logarithmic insertions AND indexing - way better than either linked lists or arrays. To avoid pointer dereferencing/locality (>>974329), store your trees in a single flat array, and calculate the offsets like in a binary tree.


 No.974398>>974523

>>974367

>logarithmic insertions

>better than arrays

in what sense? an insertion into an array is just a write to memory at a particular index, constant time.

*tilts head and looks quizzically at you*


 No.974417

>>974329

Maybe he should just write it in 6502 asm on a VIC-20, just to be sure.


 No.974444>>974928

>>974329

The only time that there is a cost to dereferencing a pointer is when you compare it to memory in cache or in register. That's not an accurate statement because most of the time memory is not stored in cache or in register, so most of the time there is no cost to dereference a pointer.


 No.974523>>974560

>>974398

Arrays are linear insertion. Linked lists are linear indexing. Trees are logarithmic insertion and indexing. You will never have an n so large that logarithmic time hurts you, but you will very frequently feel the slowdown from linear time. That's why trees are always the best choice.


 No.974560

>>974523

he's not going to ever say "I need to find a free space in this array to put this animal" though. He's going to say "this animal at this location wants to divide--is one of these four/eight positions free?"


 No.974562>>974905

>>973839 (OP)

>linked list

the b8 worked, look how many autist your triggered. HAHAHAHAHA


 No.974563>>975348

>>973839 (OP)


If(this->hunger >= TooHungryToLive)
RemoveFromList();
else Draw();


 No.974575

>>974128

>he never wrote a handcoded XORly linked list for maximum efficiency


 No.974905

>>974367

I looked into quadtrees and they sound good for what I will be going, thanks

>>974562

No bait in just new at trying to program like a white person


 No.974928>>975471

>>974444 (checked)

What a shame that a retard got those quints.

>most of the time memory is not stored in cache or in register, so most of the time there is no cost to dereference a pointer.

Read that again and then retroactively abort yourself.


 No.975348>>975421 >>975635

>All these overcomplicated solutions

If you know how many animals will there be at maximum (and you should), use an array to store all animals. Iterate over it to update it. If an animal dies, swap it with the last member of the array, and reduce its count. Then, iterate again and render.

You can do this because you don't need to keep the animals ordered to be updated, so swapping their orders is cheap. It is even cheaper than mallocing and freeing every time you update the population, and chances are that, if the user can already hold an array as big as the MAX_POPULATION, you won't need to free it any time soon. You can always make a resizable array if you want to, and it will be easier on memory, cache and CPU than a linked list. It is also better than making a 2D grid (seriously anon, what the fuck), since it will consume less memory, will iterate over no empty tiles to update, and you couple less entity data and spatial information, which will make your engine more flexible in the long run.

Also, don't use quadtrees to store the actual entity data. While it could be a good idea to build a quadtree from the entity data in order to check for collisions, it should be a "second class game engine structure", and not an actual data storage for all your game entities. Iterating over an entire array, which is what you will do in EVERY logic frame, is still cheaper than iterating over every node of any tree you can imagine.

>>974563

Don't do this. I know coupling logic and rendering in the same loop over the entity array looks like the logical thing to do, since you only iterate the array once, but it will fuck you over later on. You want to keep them separate to be able to update and/OR render (say, you want to pause the game, but still move around, like a camera mode). Iterate twice if it's needed, and you will maybe even benefit morr from code cache.


 No.975421>>975434

File (hide): 74ceb1aa7d79ca6⋯.png (8.23 KB, 300x75, 4:1, ClipboardImage.png) (h) (u)

>>975348

>Iterating over an entire array, which is what you will do in EVERY logic frame, is still cheaper than iterating over every node of any tree you can imagine.

What about iterating over a binary tree?


 No.975434>>975449

>>975421

While complexity wise is probably about the same, some implementations may be less efficient in moderately big data sizes due to jumping back and forth. Unless you implement the binary tree as an array and iterate over the underlying array or use an overcomplicated scheme to more or less iterate it linearly, but why use a binary tree if you are looking at an unordered set and not an ordered collection?

Also, if the binary tree is ordered, you will have to reorder it on reinsertions. Unless you habe a good reason to use a tree, use an array.


 No.975449

>>975434

Rethinking it, you may want to have a binary tree at some point if you want to implement scripting or direct interactions.You will have to refer to specific objects at some point in time if you want to write scripts, so ordering according to some criteria (UID?) may serve as a primitive database if sorts to search for specific objects without using a linear search.

That is, again, if you want to write a more complex engine. Whatever you do, you want to be able to iterate over items linearly and contiguously (look up Entity-Component-System) so a binary tree could do, BUT you will have worse insertion/removal times if you want to keep it ordered. Probably not an issue and hardly noticeable, but whatever. You could also build a "metadata tree" with pointers to the actual entities later on in another place, separated from the main array, specifically for searches, but you don't achieve anything other than not including the pointer to the next member in the main array if you go that route.


 No.975471

>>974928

Why don't you explain it to me since you insist on arguing.


 No.975635

>>975348

Thank you anon. I'll take all this onboard.


 No.979271

Hmm. What should it feed on. Random files and processes?




[Return][Go to top][Catalog][Screencap][Nerve Center][Cancer][Update] ( Scroll to new posts) ( Auto) 5
41 replies | 2 images | Page ???
[Post a Reply]
[ / / / / / / / / / / / / / ] [ dir / 1970floe / aov / caraota / cyoa / firechan / just / marx / o ][ watchlist ]