[BUG] Memory leak in path_find? [FIXED]

[Eckolin]

Is path_find causing a memory leak?

This program seems to use increasing amounts of memory while it runs.

Code Select Expand


program Path_leak;
   import "mod_map";
   import "mod_path";
   import "mod_grproc";
   import "mod_key";
begin
   graph=new_map(20,20,8);
   while (!key(_esc))
       path_find(0,graph,0,0,1,1,0);
       path_getxy(&x,&y);
       frame(1);
   end
end


[SplinterGU]

Don't must... but it seem have a memory leak...

[Windgate]

path_find ( ) doesn't work fine... I tried it any times and it uses LOTS of memory and is very limited. If anyone wants to check the source and fix it... Any tree algorithm could work...

But only one question Eckolin:

path_find ( ) must be used out of the LOOP and then use parth_getxy ( ) to get all positions of the path. If you use path_find () inside of the LOOP to update the path it is ok, but be sure that parameters are changed for the new x,y...

[SplinterGU]

I think that I already fix it... you have a huge sample for test it? thanks...

[SplinterGU]

fixed...

my test give me, 44 millons of frames without memory leak.

but I need a heavy test... with walls... I think that others memory leak can be happen... this implementation don't is 100% nice.

[Windgate]

my test give me, 44 millons of frames without memory leak.

Oh my lol... Here is an example with 1024 enemys solving a laberint... Each enemy re-calculate path_find on each frame, nowadays the fps can not afford more than 5 fps on my laptop.

The game has all .dll of an old version of Bennu, if you want to overwrite the dlls and check the improve come on... :P

(This example was made by a very young student last year).

DOWNLOAD: http://trinit.es/DescargaDirecta/Bennu2D/Alumnos/Victor%20Lopez/Victor%20IA%200.3.zip

[SplinterGU]

wait... 44 millons in lot of minutes...

[SplinterGU]

I think that other memory leak is present... not 100% fixed... with you sample windgate...

[osk]

I can only say that if there is not any possible solution finding a path, path_find() hangs itself, always.

[Windgate]

I have been thinking on a new path_find ( ) function made with Bennu... From the current pixel you launch one searcher to up,down,left,right pixels. The searchers do the same and launch more searchers avoiding the checked pixles (As is made on IA pathfinding). When a searcher finds the goal he returns a value and kill all active searchers... ¿What do you think about it?

The number of process could be really big on big maps, but it could be limited with a parameter or something. I have this idea cause I still don't know well how to compile dlls on Bennu :P

[Sandman]

Doing that with processes is a huge overkill, it needs to be done with two lists: checked nodes and to-be-checked nodes and then using one function iteratively is the best thing. This search is called breadth-first search. A more awesome version of this was devised by a fellow Dutchman named Dijkstra.

[Windgate]

Yes, the best thing is to use any of these algotithms. path_find use something like that, but I think it is "bad-written" or something...

[Drumpi]

But, why don't make a mod with A* algorithm? it isn't better than Dijstra?
I used Dijstra in some exercises and is better to use it with a "net" with a few points than in a pixels map, don't it?

[SplinterGU]

yes, very nice... but first need add all nodes and all conections...

the bug in current mod_path, isn't very critical, have solution... I only need change some structs...

[SplinterGU]

well, now fixed!

thanks for report...