Irrlicht Engine

Posted: **Wed Apr 30, 2008 12:54 am**

arras wrote:Here is sorted list class I use for A* pathfinding:
Code: Select all
...

If I decide to go with a list (which I most definitely will) I will definitely use this (with credit, of course

) or at least use this as a reference in learning how to make one my self.

vitek wrote:You could just use the Standard C++ Library algorithm sort...

And I will definitely look into this as well...

rogerborg wrote:Indeed, but depending on how you actually implement your object logic, you may want to go with your own bubble sort.

If you first move all objects, and then (in a separate pass) do collision / AI, then a single sort (after all the moves) will likely be more efficient.

However, if you want to do movement + AI/collision once per object, then you'll have to keep your list sorted all the time. As you noted, it's just a case of swapping objects up or down until they're back in order again. You could use a list, but an array would be just fine as well.

I've thought about this, and I think it would be necessary to update the list every time an object is moved, not just once an iteration. That's why I've decided to use a list; so that I can remove and reinsert a node without having to recopy the whole rest of the array. I want my program to be optimized for large numbers of elements in the array (>1000, at the least).

Saturn wrote:So I still fail to see how a sorted list is superior to a sorted array in this context.

If I understand correctly (which it is probable that I don't), moving an item in a list is a couple of pointer changes, whereas removing an element from an array and reinserting it somewhere else would require that the whole rest of the array be copied and moved to fit the new element in. Bear in mind, however, that I have no idea if that actually effects the situation; I'm just making an assumption.

Posted: **Wed Apr 30, 2008 1:42 pm**

Ion Dune wrote:
rogerborg wrote:However, if you want to do movement + AI/collision once per object, then you'll have to keep your list sorted all the time. As you noted, it's just a case of swapping objects up or down until they're back in order again. You could use a list, but an array would be just fine as well.
I've thought about this, and I think it would be necessary to update the list every time an object is moved, not just once an iteration. That's why I've decided to use a list; so that I can remove and reinsert a node without having to recopy the whole rest of the array. I want my program to be optimized for large numbers of elements in the array (>1000, at the least).

I imagine that what you'll be doing most often is swapping objects in the collection. That doesn't involve removal/insertion. If you use an array of pointers, then you are just swapping the value of two pointers. Literally:

Code: Select all

Object* temp = object[swapUp];
object[swapUp] = object[swapUp + 1];
object[swapUp] = temp;

A list wouldn't be significantly slower, although you'd have change at least one more pointer. They'd both be fine.

Something to bear in mind is if and how you are going to reference 'positions' in the sorted collection. For example, if your objects are spaceships, and you want projectiles (which are not actually in the list) to know their virtual position in the collection.

They could store an index to an array element, or a pointer to a list object. Both solutions would work, and both would have to re-sort the virtual position before beginning collision checking, but the index solution has the advantage of always being valid (or at least trivially boundable to the array), whereas holding a pointer to an object requires the object to stay valid as long as it's referenced.

Both do-able, of course. It really is an application dependent issue.

Posted: **Wed Apr 30, 2008 2:38 pm**

There is no difference between arrays and lists as far as sorting is concerned!

The advantage of list for insertions is offset by the need to traverse the list to get to a location. Random access to an array is O(1).

If you want to be able to cope with many nodes in a path-finding algorithm use a heap!

The situation where you use the deletion and reinsertion is actually a decrease key. A heap can do that in O(logn).

Irrlicht Engine

Sort Array