Best strategy to check all elements of a table

[Jose Marin]

Hi!

I'm testing porting some C++ code to Lua.

One part of the code checks all elements on an array
against each other.

Is there some optimized way of do this in Lua?

I don't have to check collisions twice, only one time
for each pair of objects.

In pseudocode:

for obj1 = list.first to list.end do
   for obj2 = list.first to list.end do
   
      if obj1.collideWith(obj2) then
        obj1.DoSomething(obj2)
      end
   end
end

Thanks for any tip!



__________________________________________________
Faça ligações para outros computadores com o novo Yahoo! Messenger
http://br.beta.messenger.yahoo.com/ 

[Glenn Maynard]

On Mon, May 29, 2006 at 06:57:58PM +0000, Jose Marin wrote:

> I don't have to check collisions twice, only one time
> for each pair of objects.
>
> In pseudocode:
>
> for obj1 = list.first to list.end do
>    for obj2 = list.first to list.end do
>    
>       if obj1.collideWith(obj2) then
>         obj1.DoSomething(obj2)
>       end
>    end
> end

More of an algorithm question than Lua, but you probably want (using your
pseudocode):

for obj1 = list.first to list.end do
   for obj2 = obj1+1 to list.end do
      if obj1.collideWith(obj2) then
        obj1.DoSomething(obj2)
      end
   end
end

or in Lua:

list = { "a", "b", "c", "d", "e" }
for k, v in next, list, nil do    -- same as pairs(list)
  for k2, v2 in next, list, k do  -- like pairs(list), but start at next(k)
    print(v .. ", " .. v2);
  end
end

--
Glenn Maynard

[Jose Marin]

Good, that's what I needed!
Thanks!


--- Glenn Maynard <glenn@...> escreveu:

> On Mon, May 29, 2006 at 06:57:58PM +0000, Jose Marin
> wrote:
> > I don't have to check collisions twice, only one
> time
> > for each pair of objects.
> >
> > In pseudocode:
> >
> > for obj1 = list.first to list.end do
> >    for obj2 = list.first to list.end do
> >    
> >       if obj1.collideWith(obj2) then
> >         obj1.DoSomething(obj2)
> >       end
> >    end
> > end
>
> More of an algorithm question than Lua, but you
> probably want (using your
> pseudocode):
>
> for obj1 = list.first to list.end do
>    for obj2 = obj1+1 to list.end do
>       if obj1.collideWith(obj2) then
>         obj1.DoSomething(obj2)
>       end
>    end
> end
>
> or in Lua:
>
> list = { "a", "b", "c", "d", "e" }
> for k, v in next, list, nil do    -- same as
> pairs(list)
>   for k2, v2 in next, list, k do  -- like
> pairs(list), but start at next(k)
>     print(v .. ", " .. v2);
>   end
> end
>
> --
> Glenn Maynard
>

               
_______________________________________________________
Abra sua conta no Yahoo! Mail: 1GB de espaço, alertas de e-mail no celular e anti-spam realmente eficaz.
http://mail.yahoo.com.br/

[Enrico Colombini]

On Monday 29 May 2006 20:57, Jose Marin wrote:
> One part of the code checks all elements on an array
> against each other.
>
> Is there some optimized way of do this in Lua?

Assuming I understood correctly and that you have lots of elements, a faster
way that avoids the nested loop could be:
- create a table using elements as keys and their indexes as values.
- scan the elements and check if they are in the table.

Sorry for not writing actual Lua code, but it's some time I don't write any
and I don't want to make too many syntax mistakes :-)

Step 1 will be a little more complex if you need to enumerate multiple
conflicts with the same element in step 2 (for example, the key could be a
table including both an element and its index).

  Enrico