June 27, 2011

Crawling a Graph

I got the sector crawling code done. Then I used it to walk a sector and add every linked one to a set. This set is also added to a master set of visited sectors. I step to the next sector and, if it's not in the visited set, crawl it. Repeat for all sectors to generate a collection of sets. Each set contains either a group of linked sectors or a single orphan sector.

Here's a diagram of crawling from sector 12:

Next, I take the collection of sets, pop one off, and work through the remaining trying to find two sector that are adjacent. Once I do, I give them exits to each other and merge the popped set into the target set. I repeat this until the collection only contains one set -- the entire universe:

Lastly, I got my A* path finder working. This is the first time I've experimented with path finding. I tried a variety of heuristics and had the best luck (shortest path + least crawled sectors + fastest time) with the simplest one; Chebyshev. This is comparing ABS(X1 - X2) to ABS(Y1 - Y2) and use which ever is greater. One source I read said to add the number of hops from the starting point but, again, just Chebyshev alone gave the best results. Weirdness. Could have a glitch somewhere.

I had a funny bug during my testing. I was using random.seed() so that I'd generate the same initial links every time. I ran my path finding test; 24 hops. Ran it again; 20 hops. Again; 48 hops. What the heck? I neglected to consider that sets are unordered and was linking the orphaned sectors in varying sequence. Changing the set to a list fixed this.

Two options that I have not explored are one-way exits and links between non-adjacent sectors (wormholes). Not sure if the added complexity has value.

No comments: