It is currently Mon Oct 15, 2018 10:48 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 15 posts ] 
Author Message
 Post subject: Just some optimizing -
PostPosted: Wed Sep 05, 2018 5:45 pm 
Offline

Joined: Tue Jul 01, 2014 4:02 pm
Posts: 320
For you gurus here - what would you say is the fastest way to check the value of a variable against an array of numbers? A series of compares? A small table check using an index to cycle through possibilities? Some other trick I may not be thinking of?

Would love to know what works best for you all.


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 5:54 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20656
Location: NE Indiana, USA (NTSC)
It depends on the reason that you're checking, what range the numbers have, whether the array is in ROM or RAM, etc. Could you back up and describe the larger goal?


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 6:03 pm 
Offline

Joined: Tue Jul 01, 2014 4:02 pm
Posts: 320
Oh there are a few instances, and with the variable nature of what we’re doing, plenty I’m sure I couldn’t even think of.

But here’s one example. Platform scripts have multiple tile types that could be solid. Because we don’t know what number tiles users might make them, or how many they might have (jump through, locked door, etc), we can’t just make it a fixed set.

Right now, I’m doing compares to each it should see as solid for the *land* portion of the script. I just feel like there’s probably a better wayz. It *works*, just wondering if there’s more efficient methods I’m not considering.

This is just one example.


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 6:13 pm 
Offline

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7648
Location: Seattle
Sufficiently sophisticated C compilers can detect situations in which a jump table or a string of conditionals works better.

But sometimes it's better to change your data than your code. For example, in Driar, metatiles were moved around so that one of the bits in the metatile number meant "solid" vs "background"


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 6:19 pm 
Offline

Joined: Tue Jul 01, 2014 4:02 pm
Posts: 320
Oh yes for sure. That’s how we did it with our games too. Super fast and easy.

But for this purpose, that would be difficult to control :-)


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 6:25 pm 
Offline

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7648
Location: Seattle
I think you're asking how to optimize a problem before you know what the problem is?

I mean, both my and tepples's response really come down to "there isn't a generic optimal solution". If you can move calculations to build time (resulting in e.g. using a single bit to mean solid / not), that helps. But there are situations for which it's inapplicable.


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 6:40 pm 
Offline
User avatar

Joined: Tue Jun 24, 2008 8:38 pm
Posts: 1994
Location: Fukuoka, Japan
I'm seeing this problem too in my engine and I think I know why he's asking the question. If you make a generic editor, the first thing that come to your mind is "how" to flag that metatile so it will be recognized as a solid. Since you expect that users are going to use it in any way they want and may define the flags their own way, it complicates things to define what is solid. When a tile could be "solid" and a tile could be a "ladder" but if it's the "top" of the ladder then you can walk on top of it, those problems creeps since the editor cannot know about that.

@lidnariq
I'm in the same situation right now. The solution to put block under a certain tile number as solid is brilliant and I think I should use it (would requires to update the maps but that's why I have an editor :) ).

@JoeGtake2

So I guess if it's for nesmaker (I think?) and it is generic... It's a hard problem to solve and I feel your pain. There will be need for compromise, that's the only way to do it.


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 6:45 pm 
Offline

Joined: Tue Jul 01, 2014 4:02 pm
Posts: 320
@Banshaku - yup your ladder example is spot on. You get it.

I don’t mind finding solutions with the long strings of compares. I have a few other potential tricks woth flags too. Just figured I’d see if there was anything I wasn’t thinking of :-)


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 7:58 pm 
Offline
Site Admin
User avatar

Joined: Mon Sep 20, 2004 6:04 am
Posts: 3569
Location: Indianapolis
If you only wanted solid/non-solid, you could pre-sort the tile numbers, then do a BCC/BCS against the point where the solid/non-solid are divided. Just one comparison, but that only works for the one variable you sorted it by.

If everything has to be in random order and speed is important, it's hard to beat a look-up table. If you treat the byte as 8 flags, you could put the most commonly-used ones in D7 and D6. Because you can check those with just BPL/BMI, BVC/BVS. Saves doing an AND, which isn't much, but if you use it a lot..


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 8:10 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6875
Location: Canada
JoeGtake2 wrote:
For you gurus here - what would you say is the fastest way to check the value of a variable against an array of numbers? A series of compares? A small table check using an index to cycle through possibilities? Some other trick I may not be thinking of?

If the array of numbers is sorted, you can use a binary search to find your position in it in log(n) time, rather than checking all of them. From there you'd know everything on one side is < and the other side is >. Membler's suggestion is even better if this is an array with only a few values in it, in a sorted array you only need to check the split points where the value changes.

If they can't be sorted I'd say pull out the perspective a few steps and look at the context to see if there's something you can apply. Otherwise, from this very narrow / vague / generic viewpoint sure just check 'em all.


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 8:48 pm 
Offline
User avatar

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1250
I feel like I am missing something.

Given a map, you can get a tile number from an X and Y coordinate.
Given a tile number, you can use that as an index in an array of tile information.
Given an information template that contains 8 bits or less, you have one byte per tile number.
Given an information template that contains 9 to 16 bits, you have two bytes per tile number.
Given information where one of the bits is solid, you know which bit it's in because that's defined, and similarly you know which array of bytes it's in, even if you can create arbitrary information in an arbitrary number of arrays of bytes.

Say I have a love bit, and a strength bit and a 2 bit palette value as my tile information. For every tile number, I can change any of those values, and it will be output in a byte array with 4 bits free per byte. I'm not understanding the need for comparing multiple times for the tile situation.

I guess, even assuming your abstraction levels are map->screen->tiles->types, the type number can still refer to a similar arbitrary number of arrays of bytes with known definitions in them and you end up in the same place as far as not needing multiple compares.

I guess what I must be missing is that you assume users might create arbitrary information outside the tool, but then isn't it also their responsibility to handle it? If you allow them to create types and tile definitions in the tool, the tool always knows where everything is.

Edit: I guess one more thing. Assume the user creates a "strength", "love" and "palette" definition. If they want to also use the subroutines you've written that say... eject from solid tiles, you can reserve keywords the user can add to get that behavior, and you can output the correct bitmask for the solid tile the user can use if they want to do their own stuff with the detection. Which I really think is the solution to the problem. If you provide ejection routines, and ladder routines, the user has to use your keywords. I think that's fair. If they want to add crazy love and strength bits, the tool will output where they are and they can use that info however they wish.

Edit2: So further, A generic routine will pull a tile number from the map and return it in say... Y. Then, an ejection routine (for example), will load from a tool-created define file that is which byte it's in.
Code:
jsr generic_thing_that_returns_tile_in_y
lda whichever_byte_array_the_tool_says_contains_solid,y
and #%bit_for_solid
bne tileissolid


Edit3: If they wanted to get that love bit from a tile
Code:
jsr generic_thing_that_returns_tile_in_y
lda whichever_byte_array_the_tool_says_contains_love,y
and #%bit_for_love
bne tileislove

_________________
https://kasumi.itch.io/indivisible


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 10:07 pm 
Offline
User avatar

Joined: Tue Jun 24, 2008 8:38 pm
Posts: 1994
Location: Fukuoka, Japan
In my case, the reason I have this issue is because I had the "bright" idea to use the 4 bit leftover of the pattern table attributes, which gives me a possible of 16 values. I may have to extract that data and save it in another array someday. I think I got that idea from an optimization trick a long time ago and now in hindsight, if you don't know yet your data structure, you shouldn't optimize right way :lol: So many irky things to fix ^^;;;


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 10:51 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10892
Location: Rio de Janeiro - Brazil
I'm a sucker for indexing, look-up tables and jump tables, so I really can't see many cases where I'd want to compare numbers looking for something (unless I had huge gaps in a table, and I don't consider 256 or less "huge").

I did use binary search in my old raycaster to convert ray lengths into wall heights (avoiding a division), but that was because ray lengths were 16-bit values, and I couldn't have a table that big, so I indexed the table by wall height instead and looked for the range where each ray length would be. In my newest raycaster I simply reduced the precision and the reach of rays lengths (I have about 4096 unique lengths now) and built a straight-up look-up table.

For anything that's easily countable, such as metatiles, I'd much rather have data tables for each element so I could just look stuff up by index, even if a bit of space is wasted due to gaps in the list.


Top
 Profile  
 
PostPosted: Wed Sep 05, 2018 11:14 pm 
Offline
User avatar

Joined: Tue Jun 24, 2008 8:38 pm
Posts: 1994
Location: Fukuoka, Japan
So what you means is instead of adding an attribute per metatile, you have an indexed list per attribute type? So if you want metatiles that are blocked, you just look in that list instead of checking the attribute at that metatile location? I guess on a per game basic it could be possible but for an editor, well, you have to export the data in another format.


Top
 Profile  
 
PostPosted: Thu Sep 06, 2018 5:41 am 
Offline

Joined: Tue Feb 07, 2017 2:03 am
Posts: 608
JoeGtake2 wrote:
Oh there are a few instances, and with the variable nature of what we’re doing, plenty I’m sure I couldn’t even think of.

But here’s one example. Platform scripts have multiple tile types that could be solid. Because we don’t know what number tiles users might make them, or how many they might have (jump through, locked door, etc), we can’t just make it a fixed set.

Right now, I’m doing compares to each it should see as solid for the *land* portion of the script. I just feel like there’s probably a better wayz. It *works*, just wondering if there’s more efficient methods I’m not considering.

This is just one example.


In 6502 you optimise your data not code for most gains.

You sort the tiles.
so tile 0-36 = Solid
37-42 = Jump through
43-250 = background
250-254 = door
255 = special control
Or whatever. C64 tools have an Attribute value, that you can then sort a charset by, not sure if NES tools have such a feature.

But you want to change the allocations per "tile set" then you just use variables

lda tile
cmp SolidTileNum
bcc Solid
cmp JumpTileNum
bcc JumpThrough
cmp Background
bcc Bacckground
...

And you just load the variables as an array when you switch the tileset. Of it you switch really often or mid frame you can
ldx set
lda tile
cmp SolidTileNum,x
bcc Solid
cmp JumpTileNum,x
bcc JumpThrough
cmp Background,x
bcc Bacckground
...


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 15 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group