 |
Xioustic
Newbie
Joined: 12 Mar 2009
Posts: 4
Location: SLO, CA
|
 Posted: Thu May 07, 2009 3:00 am
[3.06] Using #THREAD to Find Optimal Path Over Large Number of Vnums
|
Hey all,
My current project is taking a large list of vnums (between 10 - 35) and sorting them by the most optimal path (least amount of moves between each) possible. I use three functions:
| Code: |
// @finddistance($fromvnum,$tovnum)
$fromvnum = %1
$tovnum = %2
#IF ($tovnum = %null) {#RETURN -1}
$distance = %numitems(%pathexpand(%pathfrom($fromvnum,$tovnum)))
#RETURN $distance |
| Code: |
// @findclosest([$fromvnum],$tovnum)
$fromvnum = %1
$vnumlist = %2
#IF ($vnumlist = %null) {#RETURN -1}
$closestvnum = %null
$closestdist = 999
#FORALL $vnumlist {
$thisvnum = %i
$thisdistance = @finddistance($fromvnum,$thisvnum)
#IF (($thisdistance > 0) && (($closestdist = %null) || ($thisdistance < $closestdist))) {
$closestdist = $thisdistance
$closestvnum = $thisvnum
}
//#PRINT Testing $thisvnum.
//#PRINT Distance: $thisdistance
//#PRINT Closestvnum: $closestvnum
//#PRINT Closestdist: $closestdist
}
#IF ($closestvnum = %null) {#RETURN 0} {#RETURN $closestvnum|$closestdist} |
| Code: |
// @findoptimal([$fromvnum],$tovnum[,$maxreturned])
$starttime = @curtimems()
$fromvnum = %1 //where we start from, defaults to current location
$vnumlist = %2 //list to optimize
$maxreturned = %3 //maximum number of rooms to return
$optimalpath = %null
$vnumlist = %dups($vnumlist)
$optimalpath = %item(@findclosest($fromvnum,$vnumlist),1) //find the first one
$vnumlist = %delitem($optimalpath,$vnumlist) //remove the first match
#FORALL $vnumlist {
#IF (($maxreturned != %null) && (%numitems($optimalpath)>=$maxreturned)) {#BREAK}
$lastvnum = %item($optimalpath,%numitems($optimalpath))
$closestvnum = %item(@findclosest($lastvnum,$vnumlist),1)
#IF ($closestvnum != 0) {
$optimalpath = %additem($closestvnum,$optimalpath)
}
$vnumlist = %delitem($closestvnum,$vnumlist)
}
$endtime = @curtimems()
#PRINT Took %eval($endtime-$starttime)ms.
#RETURN $optimalpath |
Now, finddistance doesn't take long to calculate. Findclosest takes a bit of time. Findoptimal is a bunch of nested/looped findclosests. Naturally, when plugging in a large number of vnums this can take between 15 - 120 seconds to do what I need. These calculations are done relatively often in game to allow for the quickest completion of a set of tasks.
The solution to my problem appeared to lie in #THREAD. I could use a threaded process to do the calculation and then change the variable (which was visible in the status window) on-the-fly without it (temporarily) freezing all of CMUD during the process.
However, I'm not so sure this is the best solution. It has caused CMUD to crash a few times. I'd post the script but really all it is: "#THREAD "testthread" {#VA optimaltaskpath @findoptimal(,@taskvnums)}". Then it gives a generic pointer error or some error in writing data where it shouldn't be. Then CMUD gets all funky and I have to restart it.
Suggestions? |
|
|
|
|
Xioustic
Newbie
Joined: 12 Mar 2009
Posts: 4
Location: SLO, CA
|
Posted: Thu May 07, 2009 4:38 am
|
The fatal error seems to only occur when the "#THREAD "testthread" {#VA optimaltaskpath @findoptimal(,@taskvnums)}" command is linked to a trigger (which also generates the @taskvnums values, but in a prior line of the same trigger, so I assume no conflict). Could this be related?
Error reads:
Access violation at address 00C627BA in module 'cMUD.exe'.
Read of address 00000040. |
|
|
|
|
Zugg
MASTER
Joined: 25 Sep 2000
Posts: 23379
Location: Colorado, USA
|
Posted: Thu May 07, 2009 5:44 pm
|
Take a look at the #SECTION command. When using multiple threads, you need to protect access to the same memory locations (like your @optimaltaskpath and @taskvnums variables) so that only one thread at a time will modify those variables. In general, multi-threading is a very complex topic and it best used by programmers who already understand the synchronization issues involved in threads.
|
|
|
|
|
Xioustic
Newbie
Joined: 12 Mar 2009
Posts: 4
Location: SLO, CA
|
Posted: Thu May 07, 2009 7:38 pm
|
Thanks Zugg, I'll see if adding the #SECTION command where memory is being accessed in this script fixes this problem.
|
|
|
|
|
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
