View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0000735 | FSSCP | gameplay | public | 2006-01-20 10:05 | 2006-01-28 20:30 |
| Reporter | thesource2 | Assigned To | Goober5000 | ||
| Priority | normal | Severity | major | Reproducibility | always |
| Status | resolved | Resolution | fixed | ||
| Summary | 0000735: ai-chase goal doen not work for specific ships | ||||
| Description | If I set initial order for wing "atack" thay do not obey as well as they do not if I do "add-goal(GenericWing,(ai-chase(Blahblah,89))" There was no other orders, there was no protect status on ships, which must be atacked, and there was no order to ignore them. However that wing just do not follow this order. NOTE: If I order to atack my target from comm menu, everything works fine. | ||||
| Tags | No tags attached. | ||||
|
|
There was a bug that prevented certain ship class types from being attacked but that is now fixed. Check this again in the next available CVS build and if it's not fixed just repost here. |
|
|
It is not fixed in 20061123-redmenace. Check dl3-02 (Derelict) mission. Cutlass wing does not attack two Aeolus cruisers, but they are ordered to attack. |
|
|
In 20060124 it is not fixed also. |
|
|
I worked fine for me but I checked the mission itself and this would appear to also be the result of the qsort() bug fix made earlier. Basically Windows handles it differently than Linux and OS X, but I have a temporary fix until some more permanent and better suited can be coded. The temp fix will emulate the old behavior under Windows, and the (basically) correct behavior for non-Windows. Should hit CVS later today. Edit: The basic problem is that the orders (3 of them) all have the same priority and because of the undefined behavior of equal sorts it will keep switching between orders and end up in a loop, unable to decide what to do. Simply changing the priorities in the mission file to differ should fix it, but apparently the old, broken, behavior is still needed to handle this properly under Windows. edited on: 01-25-06 13:50 |
|
|
Would this be better served by using a stable sort? Quick Sort isn't stable, so equal elements aren't guaranteed to stay in their original order. Furthermore, Quick Sort achieves its worst performance when sorting sorted lists (or almost-sorted lists), which seem to be the norm in goal sorting, considering how frequently they're sorted. Should we change the sorting algorithm? I've thought about this idly from time to time without really meaning to do anything, but seeing how much this is a problem, perhaps a change is justified. I think Insertion Sort is O(n) for sorted lists and pretty good for almost-sorted lists. edited on: 01-25-06 14:41 |
|
|
My current plan is just to never have it equal, add a goal index into ai_goal itself and use the current index as the final check. That's easier, requires much less in the way of changes, and would still work with qsort(). Of course then we still have to deal with the slowness of qsort(), which can also vary based on platform. Quick Sort stability is platform dependant which is the main problem. Though it is basically unstable regardless of platfrom. I've been thinking of changing it as well, either making our own, or using a C++ style sort (stable_sort()). Going C++ would mean quite a few more changes but may be the best thing to do. What do you think? Is it worth going all the way with it or is the index idea good enough to go ahead and do, then come back to it at some point in the future? (insertion sort is O(n^2) btw) |
|
|
Changing the struct so that the values are never equal is just bypassing the problem though. If the sort is used for something else in the future we might just see the same problem pop up again. I'd be in favor of just fixing the sort and be done with it. Quick sort is not stable *in general*, so IMHO relying on a stable version of it is not a good idea (suppose someone comes along in the future and "optimizes" it). It would be better to use something stable like merge sort. I'm basing my algorithmic estimations on my understanding of how the goals are sorted: isn't it the procedure to sort the goals upon mission load and then continue to sort them every frame? If so then the vast majority of times the sort is called, it will be given a sorted list. Only once in a blue moon (from the sort's perspective) does it get a new goal, and then all it has to do is find the sorted place for that single new element. It's nothing like sorting a completely random list. This is why insertion sort is ideal. For sorted lists, insertion sort only takes O(n) time. Yes, it's O(n^2) in the average case, but the vast majority of the time this will not happen. Quick sort, on the other hand, is very bad for this: it takes O(n^2) time to sort a sorted list. :p |
|
|
Quick Sort isn't stable and I can't argue that but qsort() doesn't have to be Quick Sort, which is part of the problem. Merge Sort would be worse though wouldn't it? I thought that it was about the same speed as a Quick Sort but can have greater memory usage (O(n log n)?). It's likely I'm wrong on that though. Yes the goals will already be sorted most (likely 99+%) of the time so having something perform better on sorted lists is the best idea. So what's your recommendation (from a code like this perspective), go with C++ sorting functions and convert ai_goals to std::vector, or do something else (like create a good sorting function for our use)? I don't really have time to go the C++ route myself at this point. I am going to go ahead and commit a quick-fix (hack) which will return 1 on equals for Windows and 0 on equals for everything else. I don't want to leave it broken while something better is getting implemented. I'll skip the index check since that's just something that would have to be removed later. |
|
|
Oh, crap, it looks like qsort is a library sort. I thought it was a function that :V: had coded up. Now I see why it's such a big problem. :-/ BTW, here's a good table of sorting algorithms: http://en.wikipedia.org/wiki/Sort_algorithm Merge sort actually doesn't require much memory at all; and it works almost as fast as quick sort, with the advantage that its worst-case time is n log n, just like its best case. Heap sort would be better, but it isn't stable. I'm really not that comfortable with the std::vector stuff, having not used them very much (and especially after that latest fiasco with the warnings). So I'd prefer coding up our own insertion sort function to work with this, with the same parameters as qsort. I'll even code it myself if you tell me where it should go. :) |
|
|
In code/ai/aigoals.cpp, line (about) 2247, the calling function is prioritize_goals(). The callback function used by qsort() to sort with is the previous function (ai_goal_priority_compare()). qsort() is used only once in aigoals.cpp, but is also used in numerous other files so if you want to actually replace qsort() throughout the code (so this problem really goes away) then these are then general rules of qsort(): The one main thing, since any new function really needs to match how qsort() works, is that sorting should be done in ascending order. The aigoals compare function does so in descending order but since qsort() is used in numerous places in the code any replacement function needs to work like qsort() does. Most of the time that qsort() is used in the game it is called multiple times and usually on an already sorted list. First qsort() argument is the elements to sort, the second is the number of elements, the third is the size of each element (needs to be of size_t type), forth argument is the comaprison function which is an int taking two const void* values and returning -1 if <, 0 if =, 1 if >. If you do that then all that needs to be done is replace the qsort() calls and then all of the comparison functions can stay as they are. |
|
|
Oh - I meant "tell me where it should go" as in tell me where I should put the function - e.g. in globalincs or somewhere else. ;) So every qsort call in the codebase should be replaced by insertion_sort? |
|
|
Oops! ;) Uh, probably systemvars.cpp, maybe. It's not platform specific and is general enough to be a valid place for it. And systemvars.h is already included in many of the files so there should be many files to change for this. And I don't know if every qsort() call /should/ be replaced, but they should be able to at least. The calls in windebug.cpp, grd3dparticle.cpp, hudescort.cpp, hudtarget.cpp, missiontraining.cpp, missionmessage.cpp, and sexp.cpp should be replaced initially since they regularly deal with lists that are sorted, or partially sorted. The others could probably be left as is and replaced later if they would possibly cause a problem. |
|
|
Okay, done. :) Not tested yet but I meticulously followed the algorithm in Wikipedia and cross-checked it with a few other places across the Web. I've replaced the sorts in aigoals.cpp and the other files you mentioned, and I've removed your ugly hack. ;) Apparently there are two situations where insertion sort is the algorithm of choice: sorted (or almost sorted) lists, and lists with 10 or fewer elements. So that should help us determine where we need to use it. |
|
|
Reminder sent to thesource2 I'm sending a reminder to thesource2 since he may have gotten lost in our discussion. ;) Thesource2, can you check the next CVS build and let us know if bug 735 has been fixed? |
|
|
It's crashing on me so far. Only hudescort and hudtarget that I've seen, but it's some memory related error with the first pointer in the compare function being invalid. |
|
|
K, the bugs have been fixed. The next CVS build should work. :) |
|
|
Yes, it is fixed |
|
|
Excellent. |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2006-01-20 10:05 | thesource2 | New Issue | |
| 2006-01-22 23:40 | taylor | Note Added: 0004445 | |
| 2006-01-24 10:23 | thesource2 | Note Added: 0004452 | |
| 2006-01-25 14:38 | thesource2 | Note Added: 0004465 | |
| 2006-01-25 18:47 | taylor | Note Added: 0004467 | |
| 2006-01-25 18:47 | taylor | Status | new => assigned |
| 2006-01-25 18:47 | taylor | Assigned To | => taylor |
| 2006-01-25 18:50 | taylor | Note Edited: 0004467 | |
| 2006-01-25 19:38 | Goober5000 | Note Added: 0004470 | |
| 2006-01-25 19:39 | Goober5000 | Note Edited: 0004470 | |
| 2006-01-25 19:40 | Goober5000 | Note Edited: 0004470 | |
| 2006-01-25 19:41 | Goober5000 | Note Edited: 0004470 | |
| 2006-01-25 21:48 | taylor | Note Added: 0004472 | |
| 2006-01-25 23:24 | Goober5000 | Note Added: 0004473 | |
| 2006-01-25 23:39 | taylor | Note Added: 0004474 | |
| 2006-01-26 03:12 | Goober5000 | Note Added: 0004478 | |
| 2006-01-26 03:13 | Goober5000 | Assigned To | taylor => Goober5000 |
| 2006-01-26 04:30 | taylor | Note Added: 0004479 | |
| 2006-01-26 05:18 | Goober5000 | Note Added: 0004481 | |
| 2006-01-26 05:33 | taylor | Note Added: 0004482 | |
| 2006-01-27 07:18 | Goober5000 | Note Added: 0004505 | |
| 2006-01-27 07:23 | Goober5000 | Note Added: 0004506 | |
| 2006-01-27 15:21 | taylor | Note Added: 0004508 | |
| 2006-01-28 01:03 | Goober5000 | Note Added: 0004514 | |
| 2006-01-28 08:02 | thesource2 | Note Added: 0004522 | |
| 2006-01-28 20:30 | Goober5000 | Status | assigned => resolved |
| 2006-01-28 20:30 | Goober5000 | Resolution | open => fixed |
| 2006-01-28 20:30 | Goober5000 | Note Added: 0004531 |
