Recursive Search Algorithm

ID:167865
 
Jan 17 2006, 6:28 pm
Alright well in my current project characters can have containers to store items in, including more containers, and in those containers in those containers you can have contaiers Ad infinitum. Sort of like the folder system in Windows. The thing is I need to make sure that people don't take a folder and try to put it into one of that folders folders, so basically I need an algorithm that can search the contents of one of the containers and the containers of all of the containers containers containers or whatever. I do plan on setting a limit for the level of hierarchy but it would be nice to have a system that would work even if I decided to expand the limit.

Ill try to draw a picture of this if that wasnt clear.
[Home]
|
|
[FolderI]
| |
| |
| [FolderA]
| [FolderB]
| | |
| | [Folder1]
| | |
| | [Foldera]
| | ...
| |
| [FolderC]
|
[FolderII]
[FolderIII]
...

So what I am trying to prevent is putting FolderI inside of FolderB or any of the folders inside of FolderB. I just need a way to check because although the system I have now wont allow the actual move of the containers, it still updates the variables associated with what is in that container as if something was moved there.





This is what I sort of came up with

proc
    //The goal of this proc is to make check is src is in C or any of Cs subcontainers
    Check_Move_Container(obj/item/C) 
        if(ChkContain(src)) //This just basically checks to see if something is a container
            if(src in C) return 0
            else
                for(var/obj/item/I in C)
                    if(src in I) return 0
                    else 
                        for(var/obj/item/O in I)
                                // Gave up here because I figured out the way I was doing it, 
                                //I would never be able to accommodate all possibilities 
                                //because that would require and infinite amount of programming
        else return 1

I also tried using
while(ChkContain(C))

and the continuosly changeing C until it ran through all of Cs contents but I couldnt figure that out

Thank you in advanced for any help you can give.
Jan 17 2006, 6:36 pm
Perhaps it would be easiest to work from the bottom up instead of the top down.
proc/check_folder(A, B)
    //where A is the target folder and B is the possible destination
    while(B && B!=A)
        B=B.loc
    if(B==A)return 0
    return 1

This will return 1 if it is safe to move and 0 if it is not.

Working it backwards, you don't need to mess with all those lists of contents, since each object will only ever be inside of one other object.
Jan 17 2006, 7:05 pm
In response to Loduwijk
That is a better way of looking at it then I thought up, however I do not not see how that would work except in a case were each folder only contained one folder, if there was a situation where there was two folders in a folder then that method wouldnt work unless their was a way to run that for every case. Also it would need a way to find the lowest folder.
Jan 17 2006, 7:11 pm
In response to Drumersl
Drumersl wrote:
That is a better way of looking at it then I thought up, however I do not not see how that would work except in a case were each folder only contained one folder, if there was a situation where there was two folders in a folder then that method wouldnt work unless their was a way to run that for every case. Also it would need a way to find the lowest folder.

In a hierarchical container system like this one, that doesn't matter. The algorithm here doesn't depend at all on whether a folder has zero, one, or four hundred other folders inside. Basically all you have to do is make sure you're not storing one folder inside another that it ultimately contains. To do that, you just have to follow the destination up the tree until you find the source, if at all. If you don't find the source there, there is no danger of a circular list.

Lummox JR
Jan 17 2006, 7:25 pm
In response to Lummox JR
I really didn't expect that simple of a solution. Now that I look over it again it makes a lot more sense. Thank you both for your help.
Jan 17 2006, 7:33 pm
In response to Drumersl
Drumersl wrote:
I really didn't expect that simple of a solution. Now that I look over it again it makes a lot more sense. Thank you both for your help.

Aye, sometimes things are a lot simpler than they seem. But then, those can be some of the most satisfying pieces of code to write, because they present the opportunity to write something truly elegant.

Lummox JR