1 dimensional array to act like a 2d one?

I know I've done this before, but I've forgotten the math on how to do this. because of the way I've coded, I have a 1 dimensional array, but the data actually represents a 2d array. So instead of a 10 by 10 set of array elements, there's just a set of 100 to represent the data. I'm trying to wright a function that can take 2 indexes as if it's a 2d array and convert it to the index on the 1d array and retreive the value. Any ideas?

This should do it

array[X + Y * WIDTH]

If the 2 indexes are stored in the 1d array as a string and separated by a comma (ie... "Health,100"), you could extract them by using the split command like this:

Local index$[] = array[0].split(",")

Then index[0] would be the first value and index[1] would be the second value etc.

EDIT: Something tells me grable has the correct answer.

At the expense of some memory, you could get rid of the x+y*w math which may save some if your array usage is intensive (tho I haven't tested the performance diff).

Just make a lookup table!

local lookup:int[100]
local x:int,y:int,w:int=10
for local t:int=0 to 99
  lookup[t]=x+y*w
  x:+1
  if x>9
    x=0
    y:+1
  endif
next

for local t:int=0 to 99
  print your_1d_array[lookup[t]]
next

(untested :P)

Ha,Ha,Ha.. :)
@CS_TBL. I don't know. But isn't that code the same as this:

for t = 0 to 99
    print your_1d_array[t]
next

Hmmmmmmmm... perhaps I wasn't fully awake yet ^_^

Well ok:

lookup table should be 2d ofcoz, and each item points to a 1d-location. ^_^

One would think that it is faster to use x+y*width (with possible optimization) than a lookup table.

Maybe.. dunno, haven't checked. How would you optimize x+y*w btw?

The main optimization is getting rid of the multiply.

If the WIDTH is power of two, you can use left shifting.

Print (3 + 4 * 256)
Print (3 + 4 Shl 8)

If its not you can use a collection of shifts and additions by splitting up the number into its power of two components.

Print (3 + 4 * 320)
Print (3 + (4 Shl 8) + (4 Shl 6)) ' 3+(4*256)+(4*64)

Here is 3D position functions for determining a 1D position and visaversa

I use it in junction with bytereading and writing.

Function GetMapP(x,y,z)
	Return (MapW*MapH*z)+(y*MapW)+x
End Function

Function GetMapX(p)
	Return p Mod MapW
End Function

Function GetMapY(p)
	Return Floor((p Mod (MapW*MapH))/MapW)
End Function

Function GetMapZ(p)
	Return Floor(p /(MapW*MapH))+1
End Function

hmm..

And what if I say: "I don't know what the width will be, it's to be changed on the fly" ?

That wont work :P

Yeah, the WIDTH must be constant, unless you have some way of dynamically rewriting the expression at runtime ;)

another way to minimize multiplications is to take any unnecessary multiplications out of the inner loop.

local array%[2048]
local save%[32,64]
width = 32
height = 64
local p%=0
for y = 0 until height
   for x = 0 until Width
     save[x,y] = array[p+x]
   next
   p:+width  ' taking  multiplication out increases speed significantly

next

Optimising the integer multiplication is just so unnecessary it's just crazy. Write clean code, not 'fast' code, and profile, profile, profile.

well then. Lookup isn't faster at all.. ._. Pity, but still not as bad as having to hide a giraffe in your bathroom!

SuperStrict

Local a1:Int[100]
Local a2:Int[10,10]

For Local y:Int=0 To 9
	For Local x:Int=0 To 9
		a2[x,y]=x+y*10
	Next
Next

Local x:Int=3
Local y:Int=4
Local w:Int=10

Local old:Int=MilliSecs()
For Local t:Int=0 To 499999999
	a1[x+y*w] =t
Next
Print MilliSecs()-old

old=MilliSecs()

For Local t:Int=0 To 499999999
	a1[ a2[x,y] ] =t
Next

Print MilliSecs()-old

End

@Michael Reitzenstein
you think it's crazy but when when you are working with pixmaps, of 1024 x 768, rgba, it makes a lot of difference no matter how you look at it.

If you go that nutty and do rt ops on that sized pixmaps, I would consider using shaders. Thats their field, not a CPUs job.

then again you are assuming there is only one purpose for manipulating pixmaps. I am shure you seen several post here (one discused by Gray Alien and others) where that is not the case. my purpose for manipulationg a pixmap that size is not as obvious.

I didn't assume any purpose actually.
but in either case a shader is several magnitudes faster, does not mather what its purpose will be even if you use it to calculate a potential field to calculate ai movements in.

Operation on 1D, 2D or 3D data -> GPU will outperform your system even if you have a dual core

Operation on this kind of dataset is exactly the job of it.

well then I guess I don't understand shaders at all and I will need to look in to it, I will credit you for any lesson learned or will come and challenge you over it when I am ready.
just a little question, I posted a demo code a while back:
http://www.blitzmax.com/Community/posts.php?topic=63609#710366
do you think that can be made faster any other way, I have made it about 30% faster from what was posted by optimizing it.
or how about this one:
http://www.blitzmax.com/Community/posts.php?topic=73450#820844
if that is the case, well hell, I'll leave pixel bashing alone.

Hi Jesse,

I just grabbed the source code you're pointing to, and it took me about twenty seconds to find this line:

WritePixel(pix,xp+i,yp+j,textureimg[ttx21, tty21])

This is a completely unnecessary function call in your inner loop, because all WritePixel does is:

Function WritePixel( pixmap:TPixmap,x,y,argb )
pixmap.WritePixel x,y,argb
End Function

And so no, it doesn't 'make a difference no matter which way you look at it', because your demo (pretty cool by the way) ran fine with this much more costly implementation detail.

Instead of worrying about minor optimizations, profile the thing and find out what is REALLY slowing it down, because if you try to optimize without profiling you will be wrong, and just make your code ugly.

By the way, since you asked for speedup tips, you can inline the code from the BlitzMax pixmap code if you know what the format is in advance. Write an inline of these:

	Method PixelPtr:Byte Ptr( x,y )
		Return pixels+y*pitch+x*BytesPerPixel[format]
	End Method

	Method WritePixel( x,y,argb )
		Assert x>=0 And x<width And y>=0 And y<height Else "Pixmap coordinates out of bounds"
		Local p:Byte Ptr=PixelPtr(x,y)
		Select format
		Case PF_A8
			p[0]=argb Shr 24
		Case PF_I8
			p[0]=( (argb Shr 16 & $ff)+(argb Shr 8 & $ff)+(argb & $ff) )/3
		Case PF_RGB888
			p[0]=argb Shr 16 ; p[1]=argb Shr 8 ; p[2]=argb
		Case PF_BGR888
			p[0]=argb ; p[1]=argb Shr 8 ; p[2]=argb Shr 16
		Case PF_RGBA8888
			p[0]=argb Shr 16 ; p[1]=argb Shr 8 ; p[2]=argb ; p[3]=argb Shr 24
		Case PF_BGRA8888
			p[0]=argb ; p[1]=argb Shr 8 ; p[2]=argb Shr 16 ; p[3]=argb Shr 24
		End Select
	End Method

Find the pixel offset by inlining pixelptr and use a format in your array such that you can cast the pixel pointer to an int ptr and assign straight over.

Of course, this is the kind of optimisation that you'd make after 1) the program is too slow for your purposes and 2) after profiling it's clear that this is a speedup that'll give the highest return on investment

I never said that code was optimized. obviously I can do that and more. but I am more concerned about what Dreamora said about shaders and the like. if his method is faster why am I wasting my time with pixels.

If you know that you stay on a specific format of the above ones you can even opt it further by using memcopy instead of that many shifts and assignements.

further opts would be by not using such commands at all but doing p :+ sizeofColor to go through

=> to get the maximum out of BM use the default commands and their implementation as an idea on how to optimize it seriously for your specific need.

I made an antialias pixmap rotation program a while back to practice on pixmap I know it's pointless when you have timage to work with and image rotation but yust to illustrate the fact that I done it before here it is:

Function RotateWeightedpixel(image:TPixmap, canvas:TPixmap,startx:Int,starty:Int,sinv:Int,cosv:Int)

  Local px:Int, py:Int,pw:Int,ph:Int
  Local imagePosX:Int, imagePosY:Int
  Local tmpImagePosX:Int, tmpImagePosY:Int
  Local pixel:Int,pixeltemp:Int,x:Int,y:Int,nx:Int,ny:Int
  Local mem:Byte Ptr, canvasptr:Byte Ptr,bpp:Int,p1:Int,p2:Int,p3:Int,p4:Int
  Local r:Int, g:Int, b:Int,a:Int
  Local w1:Int, w2:Int, w3:Int, w4:Int
  Local pixelSelect:Int
  bpp = BytesPerPixel[image.format]

  pw = Canvas.Width*PRECISION  
  ph = Canvas.Height*PRECISION
  imagePosX = startx
  imagePosY = starty
  For Local n1:Int = 0 To 1
  For y=0 Until Canvas.Height Step 2
    ' Make temp copies of image counters For use in x loop
    tmpImagePosX = imagePosX
    tmpImagePosY = imagePosY
    ' Update image pos counter For Next row
    imagePosX = imagePosX - sinv Shl 1
    imagePosY = imagePosY + cosv Shl 1
    '--- Start of X-loop
    canvasptr = canvas.pixels+(y+n1)*canvas.pitch
    For x = 0 Until Canvas.Width
      pixel = clrColour ' Default colour For cleared corners
      If((tmpImagePosX>0) & (tmpImagePosX<(pw)) & (tmpImagePosY>0) & (tmpImagePosY<ph))  
		  nx = tmpImagePosX Shr 8
		  ny = tmpImagePosY Shr 8
		  px = tmpImagePosX Shr 4
		  py = tmpImagePosY Shr 4
		  px = px & $f
		  py = py & $f

		  pixelSelect = 0
		  If(px >= W2D) pixelSelect :| 4
		  If(py >= W2D) pixelSelect :| 8
		  If(px < W2H)  pixelSelect :| 2
		  If(py < W2H)  pixelSelect :| 1
 
	  	  If((nx<0) Or (ny<0) Or (nx>=image.width) Or (ny>=image.height)) 
			  p1 = clrColour
		  Else	
	    	  mem = image.pixels+ny * image.pitch + nx*bpp
			  p1 = Int Ptr(mem)[0]
		  EndIf
		  pixel = p1
		  Select pixelSelect
			  Case 1                   ' Weight two pixels, up
				If (nx<0) Or ((ny-1)<0) Or (nx>=image.width) Or ((ny-1)>=image.height) 
					p2 = clrColour
				Else	
	    			mem = image.pixels+(ny-1) * image.pitch + nx*bpp
					p2 = Int Ptr(mem)[0]
				EndIf
			    pixel = midw2(p2, p1, px-(8-BW/2), py)
    
			  Case 2                   ' Weight two pixels, Left
				If ((nx-1)<0) Or (ny<0) Or ((nx-1)>=image.width) Or (ny>=image.height) 
					p2 = clrColour
				Else	
	    			mem = image.pixels+ny * image.pitch + (nx-1)*bpp
					p2 = Int Ptr(mem)[0]
				EndIf
    			pixel = midw2(p2, p1, py-(8-BW/2), px)
    
			  Case 3                   ' Weight four pixels, up Left
				If ((nx-1)<0) Or ((ny-1)<0) Or ((nx-1)>=image.width) Or ((ny-1)>=image.height) 
					p4 = clrColour
				Else	
	    			mem = image.pixels+(ny-1) * image.pitch + (nx-1)*bpp
					p4 = Int Ptr(mem)[0]
				EndIf
				If (nx<0) Or ((ny-1)<0) Or (nx>=image.width) Or ((ny-1)>=image.height) 
					p2 = clrColour
				Else	
	    			mem = image.pixels+(ny-1) * image.pitch + nx*bpp
					p2 = Int Ptr(mem)[0]
				EndIf
				If ((nx-1)<0) Or (ny<0) Or ((nx-1)>=image.width) Or (ny>=image.height) 
					p3 = clrColour
				Else	
	    			mem = image.pixels+ny * image.pitch + (nx-1)*bpp
					p3 = Int Ptr(mem)[0]
				EndIf
    			pixel = midw4(p4, p2, p3, p1, px, py)
			  Case 4                   ' Weight two pixels, Right
				If ((nx+1)<0) Or (ny<0) Or ((nx+1)>=image.width) Or (ny>=image.height) 
					p2 = clrColour
				Else	
	    			mem = image.pixels+ny * image.pitch + (nx+1)*bpp
					p2 = Int Ptr(mem)[0]
				EndIf
			    pixel = midw2(p2, p1, py-(8-BW/2), 15-px)
    
			  Case 5                   ' Weight four pixels, up Right
				If ((nx+1)<0) Or ((ny-1)<0) Or ((nx+1)>=image.width) Or ((ny-1)>=image.height) 
					p4 = clrColour
				Else	
	    			mem = image.pixels+(ny-1) * image.pitch + (nx+1)*bpp
					p4 = Int Ptr(mem)[0]
				EndIf
				If (nx<0) Or ((ny-1)<0) Or (nx>=image.width) Or ((ny-1)>=image.height) 
					p2 = clrColour
				Else	
	    			mem = image.pixels+(ny-1) * image.pitch + nx*bpp
					p2 = Int Ptr(mem)[0]
				EndIf
				If ((nx+1)<0) Or (ny<0) Or ((nx+1)>=image.width) Or (ny>=image.height) 
					p3 = clrColour
				Else	
	    			mem = image.pixels+ny * image.pitch + (nx+1)*bpp
					p3= Int Ptr(mem)[0]
				EndIf
			    pixel = midw4(p4, p2, p3, p1, px, py)
			  Case 8                   ' Weight two pixels, down
				If (nx<0) Or ((ny+1)<0) Or (nx>=image.width) Or ((ny+1)>=image.height) 
					p2 = clrColour
				Else	
	    			mem = image.pixels+(ny+1) * image.pitch + nx*bpp
					p2 = Int Ptr(mem)[0]
				EndIf
			    pixel = midw2(p2, p1, px-(8-BW/2), 15-py)
    
    
			  Case 10                  ' Weight four pixels, down Left
				If ((nx-1)<0) Or ((ny+1)<0) Or ((nx-1)>=image.width) Or ((ny+1)>=image.height) 
					p4 = clrColour
				Else	
	    			mem = image.pixels+(ny+1) * image.pitch + (nx-1)*bpp
					p4 = Int Ptr(mem)[0]
				EndIf
				If (nx<0) Or ((ny+1)<0) Or (nx>=image.width) Or ((ny+1)>=image.height) 
					p2 = clrColour
				Else	
	    			mem = image.pixels+(ny+1) * image.pitch + nx*bpp
					p2 = Int Ptr(mem)[0]
				EndIf
				If ((nx-1)<0) Or (ny<0) Or ((nx-1)>=image.width) Or (ny>=image.height) 
					p3 = clrColour
				Else	
	    			mem = image.pixels+ny * image.pitch + (nx-1)*bpp
					p3 = Int Ptr(mem)[0]
				EndIf
			    pixel = midw4(p4, p2, p3, p1, px, py)
    
			  Case 12                  ' Weight four pixels, down Right
				If ((nx+1)<0) Or ((ny+1)<0) Or ((nx+1)>=image.width) Or ((ny+1)>=image.height) 
					p4 = clrColour
				Else	
	    			mem = image.pixels+(ny+1) * image.pitch + (nx-1)*bpp
					p4 = Int Ptr(mem)[0]
				EndIf
				If (nx<0) Or ((ny+1)<0) Or (nx>=image.width) Or ((ny+1)>=image.height) 
					p2 = clrColour
				Else	
	    			mem = image.pixels+(ny+1) * image.pitch + nx*bpp
					p2 = Int Ptr(mem)[0]
				EndIf
				If ((nx+1)<0) Or (ny<0) Or ((nx+1)>=image.width) Or (ny>=image.height) 
					p3 = clrColour
				Else	
	    			mem = image.pixels+ny * image.pitch + (nx+1)*bpp
					p3 = Int Ptr(mem)[0]
				EndIf
			    pixel = midw4(p4, p2, p3, p1, px, py)
		  End Select
      EndIf	
      tmpImagePosX = tmpImagePosX + cosv
      tmpImagePosY = tmpImagePosY + sinv
      Int Ptr(canvasptr+x*bpp)[0] = pixel
    Next
  Next
	  

  '************** Second Field *****************/
  imagePosX = startx - sinv
  imagePosY = starty + cosv
  Next
End Function

Function midw2:Int(p1%, p2%, ax%, ay%)

  Local r:Int, g:Int, b:Int,a:Int
  Local w1:Int, w2:Int

  w1 = convTableW2[(ax+ay*W2W) Shl 1]
  w2 = convTableW2[(ax+ay*W2W) Shl 1+1]
  a = ( ((p1 Shr 24)&$ff)*w1 + ((p2 Shr 24)&$ff)*w2 )  Shr  5
  r = ( ((p1 Shr 16)&$ff)*w1 + ((p2 Shr 16)&$ff)*w2 )  Shr  5
  g = ( ((p1 Shr 8)&$ff )*w1 + ((p2 Shr 8 )&$ff)*w2 )  Shr  5
  b = ( (p1&$ff)*w1 +( p2&$ff)*w2 )  Shr  5
  Return (a Shl 24) | (r Shl 16) | (g Shl 8) | b
End Function 

Function midw4:Int(p1%, p2%, p3%, p4%, px%, py%)

  Local r:Int, g:Int, b:Int,a:Int
  Local w1:Int, w2:Int, w3:Int, w4:Int
  Local convTable2:Int[] = [0,1,2,3,4,5,6,7,7,6,5,4,3,2,1,0]

  py = convTable2[py]*W4S
  px = (py+convTable2[px]) Shl 2 

  w1 = convTableW4[px]
  w2 = convTableW4[px+ 1]
  w3 = convTableW4[px+ 2]
  w4 = convTableW4[px+ 3]
  r = (((p1 Shr 16)&$ff)*w1+((p2 Shr 16)&$ff)*w2+((p3 Shr 16)&$ff)*w3+((p4 Shr 16)&$ff)*w4)Shr  5
  g = (((p1 Shr 8)&$ff)*w1+((p2 Shr 8)&$ff)*w2+((p3 Shr 8 )&$ff)*w3+((p4 Shr 8)&$ff)*w4)Shr 5
  b =  ((p1&$ff)*w1+(p2&$ff)*w2+(p3&$ff)*w3+(p4&$ff)*w4 )Shr  5

  Return (r Shl 16) | (g Shl 8) | b

End Function

it is not the complete program just the main routine.

[edited] wrong version

Jesse: No, but you said the integer multiply matters, but your code seems to run fine even though it's 100x more wasteful than an unnecessary multiply.

If you don't know how to write shaders, you're in for a world of hurt. If that's worth it to speed up this effect (or you want to learn shaders for something else), then fine, but if you just want to speed this up then you can probably do it fine in software.

Dreamora: Memcopy won't gain that code anything. It's not copying blocks around.

And a) I didn't suggest using those commands, I suggested stripping out the necessary code from them, and b) no, p:+sizeofcolor will not work because with a pixmap, pitch doesn't necessarily equal width*BytesPerPixel[ format ]. If it did, the PixelPtr code would look like

Return pixels + ( y * width + x ) * BytesPerPixel[ format ]

Do you actually, you know, read the code before having an opinion?

I need to look into shaders maybe helpful for something else. replaced the above code with the right one.

Well, a color is a block as well. Write pixel assigns 4 bytes manually. Memcopy can assign them as one block or copy them in.
But it was more a general hint when working with images or similar nicely aligned byte ptr structures, as memcopy allows you to copy around whole lines.
It makes little point to copy each color component on its own if you just could copy them as whole.

So yes I read what you wrote Michael. The memcopy for example will drastically speedup the write pixel end. but even more if you would write in more than 1 pixel like a part of a different pixmap or whatever. Something that needs a loop etc without memcopy.

But: Not opting it now and profiling it when it is finished might be the much more worthfull approach. Reason is that there might be cross relations that you do not have in now but that could in the end have beneficial effects that you kill by "over optimizing" the code by now.

There is nothing worse than "cool" programmers, that forget the global goal and performance due to their local detail working.

I also know there are "cool" programmers that spend their time criticising others while never actually helping solve problems. :)

A color is a block as well? Yes, a 32 bit one, for which there's an optimization on x86 that you might be familiar with. Memalloc() is 4 byte aligned - so cast the pointer to int, like I suggested many posts up:



Which is why I believe you didn't read my post and/or the code.

Memcopy will not speed ANYTHING up in Jesse's case. If you're talking about the general case, then sure, it's very very useful for copying blocks - just don't use it past the boundaries of a single line (there may or may not be empty space between them in a Blitz Pixmap).

I agree 100% with the profile it sentiment (well, that's the reason I got involved in this thread in the first place).

Jesse - Are you talking about me? Because I'm trying to give helpful advice here. Profile your code, find out what's slow, and fix that. It will never be what you expect. That's why I pointed out WritePixel in your inner loop, not to criticize, just to point out that it's easy to miss something that can make a big difference on even a small project. If you don't want to listen to that advice, fine, I don't really care. But trust me, it is a learning step most coders go through. Even Dreamora agrees!

of course I was not talking about you. but I assume dreamora was talking about me that is why I said that.

No, definitely not as you are asking intelligent questions and not just assuming that pushing in any available optimation will raise the end performance.

It was more a general statement on what kind of "optimation attitude" you should avoid :)

Oh right, I see. Sorry I jumped to the wrong conclusion. Best of luck, anyway.