Position Checker

[Clyde]

Hi,
 
With this I'd like it so that any newly created ovals do not occupy the same positions / space as an existing ones. I'm having problems in the position check function
 
srce + exe attached, uses tinyptc_ext and deprecated.
 
Thanks for your time and help,
Clyde.

[ninogenio]

hey clyde,

just had a quick look and it looks like your not fully testing for every situation.

also i think your testing point isnt quite where you think it is, maybe try drawing a white point at your test point for debugging.

ill have a closer look in a little while as im just stabbing at it cheers

[ninogenio]

hey again clyde after looking into it a bit more there are lots of little things controbuting to this not working.

and its hard for me to make it work untill i know exactly how you would like it too behave for example when one sphere is inside another does that sphere get omited from the list and the program move on to another.or another example when one sphere overlaps the other do you wish for that sphere to be repositoned/resized so that it just touches the other and no more the way you have the code structered just now your trying to do a bit of both and thats wheres its failing for example in your genterate ovel function you create the new ovel giving it a size and position and color before finding out if its conecting which is fine but then if there is a conection you give it a new randome size and position without checking that for collisions again so of course the new sphere could be over the top of another sphere.

also in your position function you check the new sphere against its self which is no good.

ie you should increase ovel_total before generate_ovel and then in your position function ovel_total-2 so you dont check new oval against new ovel.

i really like where your going with this clyde and i can see you have come on in leaps and bounds over this last little while.

btw your really on the right track, keep going with this!.if you need more help just give me another shout and let me know exactly how you want the collisons to be delbt with.

[Clyde]

Thankyou ninogenio.

I'd like for it to test and then reposition if its inside any of an existing one. I had it in a while...wend, but it got caught in an infinite loop.
 
Cheers 4 your help.
Clyde.

[ninogenio]

no worries mate.

i think there is going too have too be a bit of a restructer to happen because you have to test each one agains all others on screen and plot away from them remebering what ones you hit that could lead to thousads of combos, so im thinking maybe a bubblesort algorithm adding new x positions and y positions on a stack might do the trick fast enough for you. its not the easyest thing to tackle but well doable i have a couple of ideas im going to try out for you and we can then go for the easyest and hopefully fastest option.

edit - theres also another area where you will have to be carefull/clever and thats when the program gets too a point that it cannot add an oval of a certain size simply because there isnt enough room in these special cases a resize would have to happen and try to sqaush it in again. lol my mind is doing overtime now. well lets get the smaller things working first and worry about that later.

[ninogenio]

hey clyde i final got this to work i just changed the position function to bounding box checking and added a while loop also restructerd everything around a little.

now its a pretty slow way of doing things but as a great mentor that floats about here always said too me about optimizing.

1. dont do it.
2. dont do it yet.

get it working clear and good first. then you have something to work on.

Code: [Select]

#Include once "tinyptc_ext.bi"

const as integer SCREEN_WWIDTH=640
const as integer SCREEN_HEIGHT=480

const as integer MAX_OVALS=350

type ovals
    as single pos_x, pos_y
    as single radius
    as uinteger colour
end type


declare sub clear_buffer                ( byval buffer          as uinteger ptr,_
                                          byval colour          as uinteger=&hff000000 )

declare sub draw_oval                   ( byval oval            as ovals ptr )
declare sub generate_oval               ( byval new_oval        as ovals ptr,_
                                          byval x_limit         as integer,_
                                          byval y_limit         as integer )

declare sub init_demo                   ()

declare sub run_demo                    ()
declare sub update_ovals                ()

declare function create_ovals           () as ovals ptr

declare function float_rnd              ( byval lower           as single,_
                                          byval upper           as single ) as single

declare function int_rnd                ( byval lower           as integer,_
                                          byval upper           as integer ) as integer
                                         
declare function key_hit                ( byval key_char        as integer ) as integer

declare function position_check         ( byval new_oval        as ovals ptr ) as integer


dim shared as uinteger screen_buffer( SCREEN_WWIDTH * SCREEN_HEIGHT )

dim shared as ovals ptr oval_gfx( 0 to MAX_OVALS-1 )

dim shared as integer oval_total=0

dim shared as single running_timer=0.0f, spawn_timer=0.0f
dim shared as single spawn_duration=0.0f

init_demo()
run_demo()
ptc_close()

sub clear_buffer( byval buffer as uinteger ptr,_
                  byval colour as uinteger=&hff000000 )

end sub


sub draw_oval( byval oval   as ovals ptr )
   
    dim as integer pos_x=int( oval->pos_x )
    dim as integer pos_y=int( oval->pos_y )
   
    dim as integer x,y
   
    dim as integer ww
    dim as single w, yy
   
    dim as single radius=oval->radius
   
    dim as integer rad=int( radius )
   
    for y=-rad to rad
       
        yy=csng(y)
       
        w   =sqr(radius^2-yy^2)
        ww  =int(w)
       
        for x=pos_x-ww to pos_x+ww
           
            if ( x > 0 ) and ( x < SCREEN_WWIDTH-1 ) and ( y+pos_y > 0 ) and ( y+pos_y < SCREEN_HEIGHT-1 ) then
                screen_buffer( ( x )+( y+pos_y ) * SCREEN_WWIDTH )=oval->colour
            end if
        next
   
    next
   
end sub


sub init_demo()
   
    'ptc_setdialog( 0,"",0,1)
 
    if ( ptc_open( "0valTeen", SCREEN_WWIDTH, SCREEN_HEIGHT ) )=0 then
        end -1
    end if

    spawn_duration=100.0f
    spawn_timer=timer()*1000.0f
   
end sub


sub run_demo()

   While not key_hit( VK_ESCAPE )
    running_timer=timer()
      If ( spawn_timer + spawn_duration ) <= ( running_timer*1000.0f ) then
   
      clear_buffer( @screen_buffer(0) )
       
        update_ovals()
       
        ptc_update ( @screen_buffer(0) )
    spawn_timer=timer()*1000.0f
      EndIf
   wend
   
end sub


sub update_ovals()

   '
   ' let's make circles.
   '
       
      If ( oval_total < MAX_OVALS-1 ) then
           
         oval_gfx( oval_total )=create_ovals()
           
         generate_oval( oval_gfx( oval_total ),_
                           SCREEN_WWIDTH,_
                           SCREEN_HEIGHT )
           
      End if
       
     
    For a as integer=0 to oval_total-1
        draw_oval( oval_gfx(a) )
    Next
    oval_total+=1
    If ( oval_total > MAX_OVALS-1 ) then oval_total=MAX_OVALS-1
End sub


function create_ovals( ) as ovals ptr
   
   Dim as ovals ptr new_oval=callocate( len(ovals) )
   return new_oval
   
end function


sub generate_oval( byval new_oval as ovals ptr,_
                   byval x_limit as integer,_
                   byval y_limit as integer )
                   
    new_oval->colour=int_rnd( &hff000000, &hfff000f0 )
   
    new_oval->radius=float_rnd( 0.85f, 13.8f )
   
    new_oval->pos_x=float_rnd( new_oval->radius, csng( x_limit ) - new_oval->radius )
    new_oval->pos_y=float_rnd( new_oval->radius, csng( y_limit ) - new_oval->radius )
   
    Dim As Integer outcome
    outcome = position_check( new_oval )
    While ( outcome = TRUE )
   
    If outcome = TRUE Then
      new_oval->radius=float_rnd( 0.85f, 13.8f )
   
        new_oval->pos_x=float_rnd( new_oval->radius, csng( x_limit ) - new_oval->radius )
        new_oval->pos_y=float_rnd( new_oval->radius, csng( y_limit ) - new_oval->radius )
    End If
    outcome = position_check( new_oval )
    Wend
   
end sub


function position_check( byval new_oval as ovals ptr ) as integer
   
   Dim as integer outcome, a
   
   Dim as single o1_x, o1_y, o1_dist_x, o1_dist_y, distance
   Dim As Single o2_x, o2_y, o2_dist_x, o2_dist_y
   
   o1_x = new_oval->pos_x - (new_oval->radius)
   o1_y = new_oval->pos_y - (new_oval->radius)
           
   o1_dist_x = new_oval->pos_x + (new_oval->radius)
   o1_dist_y = new_oval->pos_y + (new_oval->radius)
           
   For a=0 to oval_total-1
       
      o2_x = oval_gfx(a)->pos_x - (oval_gfx(a)->radius)
      o2_y = oval_gfx(a)->pos_y - (oval_gfx(a)->radius)
             
      o2_dist_x = oval_gfx(a)->pos_x + (oval_gfx(a)->radius)
      o2_dist_y = oval_gfx(a)->pos_y + (oval_gfx(a)->radius)
           
      If ( a>0 ) Then
         If o1_x >= o2_x And o1_x <= o2_dist_x Or o1_dist_x <= o2_dist_x And o1_dist_x >= o2_x Then
          If o1_y >= o2_y And o1_y <= o2_dist_y Or o1_dist_y <= o2_dist_y And o1_dist_y >= o2_y Then
              Return TRUE
          EndIf
         EndIf
         If o2_x >= o1_x And o2_x <= o1_dist_x Or o2_dist_x <= o1_dist_x And o2_dist_x >= o1_x Then
            If o2_y >= o1_y And o2_y <= o1_dist_y Or o2_dist_y <= o1_dist_y And o2_dist_y >= o1_y Then
              Return TRUE
            EndIf
         EndIf
      End If
   Next   
   
   Return FALSE
   
end function



function key_hit( byval key_char as integer ) as integer
   
    if (getasynckeystate(key_char) = -32767) then
        return true
    else
        return false
    end if
       
end function


function int_rnd( byval lower as integer,_
                   byval upper as integer) as integer
   
    dim as integer value, dist, temp
   
    if upper < lower then
        temp=upper
        upper=lower
        lower=temp
    end If
   
    value=lower
    dist = abs(lower-upper)
   
    return ( rnd(1)*dist) + value

end function


function float_rnd( byval lower as single,_
                    byval upper as single ) as single
   
    dim as single temp, value, dist
   
    if upper < lower then
        temp    =upper
        upper   =lower
        lower   =temp
    end if
 
    value   = lower
    dist    = abs(lower-upper)
   
    return (rnd(1)*dist) + value

end function

i think you can still yous your position function in place of mine but you have to be a bit more carefull about where your check point is.

i just wanted to post it working to give you a good place to start from.

refering to above id like to see this becoming clever and working out how much space is available so that when space starts running out the engine can resize the new spheres based on that.

also i still think yousing some sort of a sorted stack where you already know where the best place to plot a sphere is rather than checking checking checking and checking again

any thing else just give me a bell.

[Clyde]

thankyou so much!

[ninogenio]

no problem clyde,


what i would maybe do the now is put a check inplace so that once the while loop goes through a cetain number of iterations it drops through i just went up too 5500 ovals and near the end the while loop just kept going as there was no more space left.

so what you could do is say after x thousand operation (where x is just try diffrent things till your happy you want to obviously give the while loop some time to find space but not too much ) raise a flag to let the program know it cannot create any more and to drop through the while loop.and just draw the ones up to that point that way you could actually stop doing any processing on the ones generated. and get full speed back.

[Clyde]

That sounds like a cool plan, where would you put such a test? as the attempt below isn't right.

Code: [Select]

    dim as integer outcome, attempts=0
    outcome = place_test( new_oval )
    while ( outcome = TRUE )
   
    If outcome = TRUE Then
            new_oval->radius=float_rnd( 18.85f, 64.8f )
   
        new_oval->pos_x=float_rnd( new_oval->radius, csng( x_limit ) - new_oval->radius )
        new_oval->pos_y=float_rnd( new_oval->radius, csng( y_limit ) - new_oval->radius )
   
            attempts+=1
           
        end if
    outcome = place_test( new_oval )
       
        if attempts=4 and outcome=TRUE then
            outcome=FALSE
            ovall_total=oval_total-1
        end if
   
    wend

Cheers,
Clyde.

[ninogenio]

this makes it work.

Code: [Select]

sub generate_oval( byval new_oval as ovals ptr,_
                   byval x_limit as integer,_
                   byval y_limit as integer )
                   
    new_oval->colour=int_rnd( &hff000000, &hfff000f0 )
   
    new_oval->radius=float_rnd( 0.85f, 13.8f )
   
    new_oval->pos_x=float_rnd( new_oval->radius, csng( x_limit ) - new_oval->radius )
    new_oval->pos_y=float_rnd( new_oval->radius, csng( y_limit ) - new_oval->radius )
   
    Dim As Integer outcome
    Dim As Integer itterations
    outcome = position_check( new_oval )
    While ( outcome = TRUE And oval_total < MAX_OVALS )
   
    If outcome = TRUE Then
      new_oval->radius=float_rnd( 0.85f, 13.8f )
   
        new_oval->pos_x=float_rnd( new_oval->radius, csng( x_limit ) - new_oval->radius )
        new_oval->pos_y=float_rnd( new_oval->radius, csng( y_limit ) - new_oval->radius )
    End If
    outcome = position_check( new_oval )
    itterations += 1
    If itterations > 10 Then MAX_OVALS = oval_total
    Wend
End sub

you will have to change MAX_OVALS to a shared integer insted of a const. because the MAX_OVALS has just been changed then it skips a lot of test further up in the code.

it works quite well you might like to use seconds in the while loop instead of itterations as then it will give the while loop the same time on every pc.