0

Say that you have sorting already worked out for a sweep and prune broad phase collision detection. In the case that it is already sorted, would a linked list be better suited or a vector? Is one preferable over the other? faster? more manageable?

And say now say they're not sorted and I'm referring to the entire process of sweep and prune. In this case, knowing that you have to maintain a sorted list, or have to resort a list each update in some way and than do the broad phase collision detection, same question. Is one preferable over the other for some reason, or is faster, or more manageable than the other?

possibly helpful info:

  • this is for a 2D game engine (so only concerned about x and y coordinates)
  • only working with rectangles (so AABB collisions only)
Charles Hetterich
  • 171
  • 2
  • 10
  • Bjarne Stroustrup says linked lists are slow on modern hardware: https://www.youtube.com/watch?v=YQs6IC-vgmo – Jeremy Friesner Nov 11 '14 at 05:21
  • @JeremyFriesner from what I read in the redirect question, it seems as though a linked list would be the optimal choice, since there is a lot of insertion and deletion in the middle, since I am attempting to maintain an ordered sequence of elements, and when it comes to broad phase time, all I am doing is running through the list. But from what Bjarne Stroustrup said in that lecture, no matter what the sequence is for, when running through a linked list, you are essentailly performing a random access to different locations in memory several times in a row which is signifigantly slower than a – Charles Hetterich Nov 11 '14 at 05:41
  • 1
    vector because a vector performs only one random access directly to the desired location in memory. And so in the end, in the real world, there is never a good fit for a linked list when dealing with any sequence of data that is even relatively large. Is this all correct? I would just like some clarification. – Charles Hetterich Nov 11 '14 at 05:43
  • That's my understanding of Bjarne's talk, yes -- that for a CPU whose native execution speed is much faster than the RAM system's speed (read: any modern CPU), the performance of a vector will (counterintuitively) beat that of a linked-list, because cache-hit-ratio is the main determinant of performance. Don't take his word for it though, come up with a performance test and measure the execution speed (both ways) for yourself; it's always possible that he's wrong for your particular use case. – Jeremy Friesner Nov 11 '14 at 15:47

0 Answers0