Pathfinding problem

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|30\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> Blitz -> Pathfinding problem
Mon, 29 Dec 2008, 04:39
Paul	HI! I'm making a pathfinding code. The problem is that it gets slower and slower the more I use it. I've isolated the slowdown to these lines of code, but I find nothing wrong with them. It gets so bad that it only manages 2000 iterations a second. Const t0 =2^0 Const t1 =2^1 Const t2 =2^2 Const t3 =2^3 ... Const t20=2^20 Const two20=2^20-1 Dim Fs(two20) Type Square Field x,y Field F Field G Field H Field n Field n2 Field Previous.Square End Type tmp=MilliSecs() For o.Square=Each Square p=t19+((o\F And t18) Shr 17-1) Shl 18 Fs(p)=0 p=p +((o\F And t17) Shr 16-1) Shl 17 Fs(p)=0 p=p +((o\F And t16) Shr 15-1) Shl 16 Fs(p)=0 p=p +((o\F And t15) Shr 14-1) Shl 15 Fs(p)=0 p=p +((o\F And t14) Shr 13-1) Shl 14 Fs(p)=0 p=p +((o\F And t13) Shr 12-1) Shl 13 Fs(p)=0 p=p +((o\F And t12) Shr 11-1) Shl 12 Fs(p)=0 p=p +((o\F And t11) Shr 10-1) Shl 11 Fs(p)=0 p=p +((o\F And t10) Shr 9 -1) Shl 10 Fs(p)=0 p=p +((o\F And t9 ) Shr 8 -1) Shl 9 Fs(p)=0 p=p +((o\F And t8 ) Shr 7 -1) Shl 8 Fs(p)=0 p=p +((o\F And t7 ) Shr 6 -1) Shl 7 Fs(p)=0 p=p +((o\F And t6 ) Shr 5 -1) Shl 6 Fs(p)=0 p=p +((o\F And t5 ) Shr 4 -1) Shl 5 Fs(p)=0 p=p +((o\F And t4 ) Shr 3 -1) Shl 4 Fs(p)=0 p=p +((o\F And t3 ) Shr 2 -1) Shl 3 Fs(p)=0 p=p +((o\F And t2 ) Shr 1 -1) Shl 2 Fs(p)=0 p=p +((o\F And t1 ) -1) Shl 1 Fs(p)=0 p=p +((o\F And t0 ) Shl 1 -1) Fs(p)=0 Next clean=(MilliSecs()-tmp) --v
Mon, 29 Dec 2008, 05:06
Jayenkai	Well, if you're constantly adding squares, be sure that you're removing them afterwards, otherwise it's just going to become a bigger and bigger for-loop.. Stick a counter in to be sure.. NoSquares=0 For o.Square=Each Square NoSquares=NoSquares+1 next Debuglog NoSquares --v and keep your eye on it.. -=-=- ''Load, Next List!''
Mon, 29 Dec 2008, 06:24
Paul	That was my initial thought too, but I'm deleting them in another loop a little later so, no problem there. Did the counter as well and got expected results.
Mon, 29 Dec 2008, 06:28
shroom_monk	If you're deleting them in a later loop, they're still slowing down the first loop, right? Or have I missed something? -=-=- A mushroom a day keeps the doctor away... Keep It Simple, Shroom!
Mon, 29 Dec 2008, 06:31
Jayenkai	Hmm... Um...? shrugs Nothing in FS that's doing it? .. Try doing it without the FS part, and see if it still slows down. If it IS still slowing down, then I'd guess it could be a dodgy math problem.. That'd be quite an issue if it is! -=-=- ''Load, Next List!''
Mon, 29 Dec 2008, 07:00
Paul	Oh, sorry FS is an array added declaration to original code Edit: Tried it without the fs and I get the same slowdown... strange. Edit2: Actually tried to take away everything inside the loop and get the same slowdown tmp=MilliSecs() For o.Square=Each Square Next clean=(MilliSecs()-tmp) --v
Mon, 29 Dec 2008, 08:32
Jayenkai	Then, my guess is that it's happening elsewhere.. I can't imagine that it's a simple loop that's causing it. -=-=- ''Load, Next List!''
Mon, 29 Dec 2008, 08:59
JL235	If the loop is taking longer and longer then the cause must be because the number of elements being iterated over is increasing. Inside the loop all that is occuring is addition, subtraction and some bitwise operations. It contains nothing like defining new arrays or creating new types. Besides without understanding the algorithm people can only guess at what's happening. No comments, the variable names give no explination of what they are for and it's just a snippet of the real code. One last thing: Dim Fs(two20) --v Is two20 actually defined anywhere? Shouldn't it be t20? If two20 doesn't exist then if I remember correctly it will still be valid and just contain 0.
Mon, 29 Dec 2008, 09:21
Paul	Added two20 definition to top code. This is getting really strange: tmp=MilliSecs() o.Square=First Square clean=(MilliSecs()-tmp) --v This sets clean to 0 first few times i run the function but after leaving it running for about a minute clean gets closer and closer to 50 and stays in that region.
Mon, 29 Dec 2008, 10:05
Paul	Fixed it Instead of using blitz' for a.square=each square I manually kept track of the square before each square and then by getting the last square I can iterate through the list backwards. Type Square Field prvs.Square End Type o.Square=Last Square While o<>Null oo.Square=o o=o\prvs Delete oo wend --v
Mon, 29 Dec 2008, 10:08
Jayenkai	Good idea.. So, is that all it was!?
Mon, 29 Dec 2008, 17:55
JL235	Perhaps you were making extras which are outside of the linked list. I'd leave it running for a while and watch the memory usage to make sure you don't have a memory leak.
Tue, 30 Dec 2008, 04:48
Paul	@Tikihead To sum it up: The problem was that the "for each" loop was getting very slow after a while. I also noticed that the "First" command was affected to. "Last" worked as it should. So instead of letting blitz do a "for each" i kept track of the order and did it manually. @JL235 As far as i know all types are automatically stored in linked lists. So any extras there should automatically be added to blitz internal linked lists. It does however have a memory leak, but stops after about 20 megabytes.
Tue, 30 Dec 2008, 05:03
JL235	They are stored in a list, yes, but your building your own linked list too. Unless you delete them, any you remove from your list will still be in Blitz's internal list. I suspect you aren't properly deleting them because the contents of your list should be identical to the contents of the Blitz internal list. I suspect they aren't because one should not take dramatically longer/shorter to iterate over then the other. This is not normal behaviour. 20mb isnt a strange amount of memory to be using. It could even be all internal stuff (although I'd doubt it). Plus how long did you leave it running for, just until the memory stopped going up? I'd leave it for at least an hour.
Tue, 30 Dec 2008, 06:57
Paul	Been having it on since you posted. The memory usage went up with 30 MB during the first five minutes and then stayed in the same area the rest of the time. Deleting all the types with Blitz' lists didn't release any memory. So as i see it, the extra memory is something that blitz does internally.