Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

AppGameKit Classic Chat / Best way of searching within a Type? Array / Type question

Author
Message
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 21st Sep 2018 18:51
Hi everyone,

I've got a array of tiles, which is filled with entities that are also stored using the type structure. So for each individual tile there are like 5 different properties I can store and search for.

However….. one of those properties is a String, but for some reason I can not seem to find which command to use for specifically searching for String. I'm pretty sure it works with .find for arrays, but I'm guessing
because it is a Type instead of an 'array', it fails?

It's weird, because using the .insert command I can add new Strings to it as if it's a regular array. But... removing a String from that list seems impossible?

In short, what am I missing here?



in my code I'm using the following to store the data;




Any tips on how to search through type containers or arrays? The problem is.. my levels are procedurally generated, so I am going to have to determine what a certain tile turned into.
Golelorn
7
Years of Service
User Offline
Joined: 20th Nov 2016
Location:
Posted: 22nd Sep 2018 13:54 Edited at: 22nd Sep 2018 13:58
Make your own functions that will search the array. Quick example below.

PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 24th Sep 2018 12:38
Thanks a lot Golelorn!

Yeah, I was using something similar to make individual enemies do things based upon location and also get the ID of tiles clicked after ray trace etc. So I guess this kind of search routine is the only way of directly finding / pointing to an entity (when the ID is unknown)??



I've noticed that letting 10000+ entities check whether they are in view using a continuous search this way is really able to slow things down. I got it to run faster by using some code to only run every 60th tick, But apparently those for i loops aren't that fast? Anyway, just rambling now. Thanks again!



Phaelax
DBPro Master
20
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 24th Sep 2018 13:44
If you're searching by the same field/property every time and the array doesn't change very often, you can manage a sorted array and use a binary search that will be substantially faster than a sequential search of that size.

Another helpful tidbit, if create a search function and you know the array is going to be very large, pass the array by reference instead of by value. On larger arrays you will see a noticeable speed increase.


One last thing that might speed it up a little, I imagine string comparisons are slower than looking for an integer value. I don't know what kind of string values you're storing, but it might be possible to replace those strings with numbers. So if there's only a few different values you use for typeBlocks, you can do something like this:



The string array is really just to reference whatever string values you actually need there. If it's just a matter of having something descriptive to help look up elements, then name your constants will good descriptive names and you can ignore the extra string array, if you understand what I mean.
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
Golelorn
7
Years of Service
User Offline
Joined: 20th Nov 2016
Location:
Posted: 24th Sep 2018 13:54
I think I would narrow down your selection to tiles that are within X distance from the center of the screen? Is that an option?



GarBenjamin
AGK Developer
7
Years of Service
User Offline
Joined: 30th Nov 2016
Location: USA
Posted: 24th Sep 2018 14:34 Edited at: 24th Sep 2018 14:35
A virtual grid can be used to optimize identifying sprites and 3D objects within a certain area (in general game dev I mean same could be done for tiles. If familiar with the the old "dirty rectangles" method of screen draw optimization is sort of kind fundamentally similar but not really.

Basically every object stores its id in a virtual grid cell. This would be a grid of arrays for each cell. The grid itself could be screen-sized or 16th screen size etc. When querying objects within a certain point basically just check only the start cell (i.e. where point of search begins) grid cell list and any neighboring grid cells as needed. For a circle or square the start cell is center. For ray be start of line. Same thing should be possible with tiles as well.

This kind of thing will just add a lot of overhead to a small game world for no reason. But when world is large with numerous entities to manage the more it becomes useful.
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 25th Sep 2018 00:51
Quote: "I think I would narrow down your selection to tiles that are within X distance from the center of the screen? Is that an option?"


Yeah, that's actually a good idea too. I will probably use a fairly strong fog anyway and have mostly only tiles loaded and visible that are close to the player and or camera.

@Phaelax:

Thanks a lot, passing it by reference probably is a good idea.

Quote: "The string array is really just to reference whatever string values you actually need there. If it's just a matter of having something descriptive to help look up elements, then name your constants will good descriptive names and you can ignore the extra string array, if you understand what I mean."


Yeah, honestly string arrays aren't that practical anyway it seems.

In the Type I have something like : typeblock as string [0]

..but that also means that any time I want to compare such a string directly, you'd get something like tiles[index].typeblock[0] where any results have to be or support strings. Even worse, when you try to write it into a save file of some kind, I've already noticed it seems to add the index number together with the string. So yeah, I most likely will have to a switch to integers and just define and search for enemy types that way. I was just hoping it would make things a bit more workable / readable using strings, but that seems a mistake. To be fair, it was also a bit of an experiment, as I am also making a database orientated app that is very string heavy, so tried to learn about using strings in types and arrays like this.
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 25th Sep 2018 01:01
Speaking of 'large worlds' by the way, does this engine do backface culling on it's own even for more extreme cases?? I couldn't really find much clues, except for SetObjectScreenCulling , which is turned on by default anyway and not really the thing I am looking for.

I'm sure you guys know how a lot of games nowadays are build using modular level assets with a lot of overlapping polygons of assets crossing other assets basically, instead of cleanly modelled assets with proper polygon counts. Would such a thing be even possible with AppGameKit ?
MillaSays
6
Years of Service
User Offline
Joined: 15th Dec 2017
Location:
Posted: 25th Sep 2018 09:44 Edited at: 25th Sep 2018 11:32
Going through an array from zero until you find the correct value may be fine for small array-sizes. But for bigger arrays, some more finesse is needed. So I created a little demo-project that creates a type-array containing 9999 items. The usual number of iterations to find a given number or string is somewhere between 12 and 18 at that size. Doing it the more naive way, it would be anything from 1 to 9999...

code is at github ready to be cloned: https://github.com/rDybing/sortFind

Or do the copypasta from here:



I'm not too fond of comments in code, so if you got questions or something is unclear, just ask

(oops, posted this using my work account - I'm also here under the username Dybing, which is my private account)
Phaelax
DBPro Master
20
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 25th Sep 2018 13:57
If you have sorted data (if possible), a binary search would still result in a max iteration of less than 12 with 1000 elements.
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
Bengismo
6
Years of Service
User Offline
Joined: 20th Nov 2017
Location: Yorkshire, England
Posted: 25th Sep 2018 14:38 Edited at: 25th Sep 2018 14:40
The op mentions 10,000 entries and the example provided above is for 9,999... ...a search through just 1000 would be 10 iterations (worst case). 10,000 is 14 iterations (worst case)

The built in .find() function works well and uses a binary search so provided you just ensure your ID is the first item in the type then the built in functionality will find the item your looking for. Id use the built in search as it will be way quicker then any interpreted basic one will be.

If its an array of tiles then it may not be necessary to store the x,y,z in a list of tiles as there location in the array would give the location x,y,z values anyway. So each locations is just an id and maybe a string...if wanted.
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 25th Sep 2018 14:39 Edited at: 25th Sep 2018 14:39
@Dybing: that's very interesting! Will have to dig through that code tonight somewhat to better see the approach. Thanks very much.

I'm getting ~16 iterations with 40000 arrays, which is more than fast enough for what I need.
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 25th Sep 2018 15:17
Quote: "If its an array of tiles then it may not be necessary to store the x,y,z in a list of tiles as there location in the array would give the location x,y,z values anyway. So each locations is just an id and maybe a string...if wanted."


Well, it may appear redundant in how using something like GetObjectX( tiles[index].ID ) would return the current X as well, and I guess to some extent just multiplying the index by the spacing and size of the tiles should give a good approximation of the location too, but sometimes it's just nice to keep track of locations by storing them explicitly (for example, when saving a level that was randomly generated and then trying to load it back again. At that point positions are kind of relevant enough to store). Comparing just two numbers should always be faster than using two GetObjectX( tiles[index].ID ) type lookups as well, right?

I may reconsider later though, as there might not be very many changes to the locations of tiles ever and pathfinding might not even need it (or rather, I will most likely limit enemies moving around to a limited areas where they were spawned from anyway).

I appreciate the insight nonetheless. You're certainly not wrong!
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 25th Sep 2018 15:27 Edited at: 25th Sep 2018 15:30
Some shots of what it's about :


A bit of a stress test situation, normally this won't be all visible for sure. But have a problem with my code to set stuff to invisible at certain distance:




Actual level generation is still too random, but that will be dealt with eventually.

Attachments

Login to view attachments
Bengismo
6
Years of Service
User Offline
Joined: 20th Nov 2017
Location: Yorkshire, England
Posted: 25th Sep 2018 15:30 Edited at: 25th Sep 2018 15:37
That looks nice, I like the fun textures used.

In the tilemap library i use the location is derived from the index using / and mod and gives an exact location fairly easily. Same with the 3D block based system I used too where each block was different but didnt need to store any location as the index always gives you that. Its very easy to go from Index to x,y,z and x,y,z to index. I got >100k blocks and still managed over 60fps so should be doable if you combin ehtem into chunk objects

Its the same on loading/saving too...the positions arent needed unless it is no longer located on a tiled grid, but then its not a tile if its not on that grid anyway.

Its just saving a load of data and the find() function works really well and faster than the loop code to iterate through array locations with it being assembly vs interpreted basic.
Dybing
12
Years of Service
User Offline
Joined: 12th Sep 2011
Location: Bergen, Norway
Posted: 25th Sep 2018 16:35
@PHeMoX My routine is actually a Binary Search, manually implemented as I understood you needed to find a value within an arbitrary variable of a type-array. In the code there is a bit of repetition going on, as you can't overload AppGameKit function C# style or use an interface Go style. But nonetheless. Using this method you can find any value in a type-array by simply copying to sorted type-arrays, one for each variable in the original type array. Seeing as you can't use the AppGameKit find method on type-arrays, only ordinary arrays (AFAIK). It'll eat a bit of memory - but is super efficient in terms of speed.

And the transfer from original type-array to sorted arrays you can do between levels or at some other convenient event where time is not critical.
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 25th Sep 2018 17:06 Edited at: 25th Sep 2018 17:12
@Bengismo: Thanks man, yeah trying to go for a pretty friendly style.

Quote: "I got >100k blocks and still managed over 60fps so should be doable if you combin ehtem into chunk objects"


How do you update those blocks though? I now have a pretty crude approach of not checking visibility / range to camera more often than once every 60 frames. This helps a lot in performance as you can imagine. Just letting it update continously gets slow with really only a few hundred blocks really (on mobile at least). I guess I need to group tiles in larger groups, so I can let the code skip even checking those as they're too far away somehow.


@Dybing:
Quote: "And the transfer from original type-array to sorted arrays you can do between levels or at some other convenient event where time is not critical."


Yeah, there is only a level generation at start-up at the moment. So I can transfer them right after that I think. To be honest though, I haven't yet got a good understanding of sorted arrays yet.

Quote: "Seeing as you can't use the AppGameKit find method on type-arrays, only ordinary arrays (AFAIK). "


Yeah, I don't think the .find is usable on type arrays, at the very least I haven't managed to get it working. It also still requires an index anyway, so you'd still have to first check whether the stored ID of an entity matches the ID of the index you search through anyway.

If I understand properly, just using .find without an index means it will search the first possible index, right?
Dybing
12
Years of Service
User Offline
Joined: 12th Sep 2011
Location: Bergen, Norway
Posted: 25th Sep 2018 18:15 Edited at: 25th Sep 2018 18:33
@PHeMoX

> I haven't yet got a good understanding of sorted arrays yet.

Think of it as a lookup table. From the original type-array you make several type arrays - or lookup-tables if you wish. When transferring, you transfer the primary values from original type-array that you want to sort on to their own type-arrays *and* the index where that value can be found in the original type array. This then get sorted on the primary value in each of these look-up table arrays.

When you do the Binary-Search on the sorted type-arrays, you just extract the index stored there, and use this index value on the original type-array. Simple.

In other languages, you do much the same thing but set it up as a map (or dict as in dictionary) - a special kind of array where the index is the primary value, and what is stored is the index of the original type - and just look up the value with built in commands. But alas, in AppGameKit one need do it manually. Which isn't entirely bad, as it do teach one what goes on under the hood of more fully featured languages
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 26th Sep 2018 00:06
Thanks, I really appreciate it Dybing.
Phaelax
DBPro Master
20
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 26th Sep 2018 16:09
Quote: ".a search through just 1000 would be 10 iterations (worst case). 10,000 is 14 iterations (worst case)"

Oops, I misread it. Ignore me, I'm old and senile.
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds

Login to post a reply

Server time is: 2024-03-28 21:37:52
Your offset time is: 2024-03-28 21:37:52