Looking for some help with an algorithm... (ACS)

[EarthQuake]

Okay, before I get started, let me explain my situation...

I have a grid of sectors, each being a room that is connected to all adjacent rooms via a doorway. It might look something like this:

   ###########   ###########   ###########
   #         #   #         #   #         #
   #    1    # G #    2    # J #    3    #
   #         #   #         #   #         #
   ###########   ###########   ###########
        A             B             C
   ###########   ###########   ###########
   #         #   #         #   #         #
   #    4    # H #    5    # K #    6    #
   #         #   #         #   #         #
   ###########   ###########   ###########
        D             E             F
   ###########   ###########   ###########
   #         #   #         #   #         #
   #    7    # I #    8    # L #    9    #
   #         #   #         #   #         #
   ###########   ###########   ###########

Where 1-9 is the room (or "cell" as I will call it), and A-L is a doorway between two cells (I will call these "connections"). The ordering is just arbitrarily chosen, and doesn't necessarily make any sense in the algorithm I'm trying to figure out.

What I'm trying to do (this is related to ACS) is trace a path from a randomly chosen cell to another cell, to create a randomized layout of sorts. All connections not part of this path are made inaccessible. What I am having trouble implementing though, is an algorithm that can take a known cell index (or even the coordinates of that cell) and determine the tag of any of it's connections (which actually varies depending on if that cell is on the corner or edge of the grid).

Basically, I'm trying to come up with a function that looks something like this:

Tag = GetConnectionTag(Cell, Direction);

Where "Tag" is literally a unique tag assigned to each doorway sector, "Cell" is the unique index of the room I'm currently working from (1-9 in the above example), and "Direction" is some constant used for specifying which connection I want to examine. If a given cell does not actually have a connection in the specified direction, the function would probably return a tag of zero, from which I could abort operation. The tags used for the connections will obviously depend on the algorithm itself, each being unique.

I have the following known information: the maximum size of the grid, the unique cell index, the cell X/Y coordinates, and the direction of the connection to check.

Again, the order I've used in my illustration is arbitrarily chosen. Ideally, connections A-L would have values that coincide with their actual sector tags, but I do not know what values these would be. I've busted my balls trying to wrap my head around all the math, and even dragged a friend of mine into this who is much brighter than I am, but still, no solutions come to mind. So as a last resort, I'm asking the Doom collective mind for help!

I don't know if there is a simple solution to this, but I would really appreciate some help, as I have a project that depends on a clean implemention of this. Thanks much.

[tempun]

Well, if sector tags are shuffled in an unknown way, the task looks hopeless, as ACS, AFAIU, doesn't provide a way to inspect level geometry. If you can choose the order of sector tags, then your task is rather easy.

[andrewj]

In OBLIGE, I use the digits on the numeric keypad for directions, e.g. 2 = south, 8 = north, 4 = west and 6 = east.

So for a cell with an X coordinate from 1 to 9, a Y coordinate from 1 to 9, and direction from 1 to 9, let the tag be "base + X*100 + Y*10 + D" e.g. if the base is 1000 then for X=3, Y=4, D=2 the tag will simply be: 1342.

[TimeOfDeath666]

What about giving the doors specific tags, writing a script for all possible routes/scenarios, and just randomly choose which script to run?

[Phobus]

To do this sort of randomisation the starting base needs to be well structured. andrewj seems to have a pretty good method for you I'd say.

I'd love ot be a bit more helpful, but this is the sort of thing I can't explain... I'd have to make an example myself first, which would probably take longer than somebody coming up with a good explanation.

[EarthQuake]

Andrewj was on the right track with this, but it didn't take into account that connections were shared between cells.

A couple of friends actually conquered this quest. Given a cell layout like above, using this (note the X and Y axes are mistakenly swapped) as the tagging scheme, the following function does exactly what I originally set out to do:

// Width and height of dungeon in terms of number of cells.
#define GRIDSIZE 5

// Constants used to refer to a direction from within a cell...
#define DIR_N -GRIDSIZE + 1
#define DIR_S GRIDSIZE
#define DIR_W 0
#define DIR_E 1

// Returns tag of connection in specified direction from a cell,
// or zero if no such connection exists in that direction. X and
// Y are the coordinates of the cell (base 0).
Function int GetConnectionTag(int X, int Y, int Direction)
{
   // Do bounds checking...
        If (Direction == DIR_N && Y == 0)            Return 0;
   Else If (Direction == DIR_S && Y == GRIDSIZE - 1) Return 0;
   Else If (Direction == DIR_W && X == 0)            Return 0;
   Else If (Direction == DIR_E && X == GRIDSIZE - 1) Return 0;

   Return Y * (2 * GRIDSIZE - 1) + X + Direction;
}

Basically since the tags are defined from left to right, top to bottom, the direction parameter is used to "step" forwards or backwards along this range, with north and south directions taking a larger step (roughly equal to the grid's width/height). Because looking east from cell (4,0), where there is no connection, would actually return the same tag as looking north from cell (0,1), some bounds-checking had to be implemented. This function also assumes the grid is square, but it should be relatively easy to separate GRIDSIZE into width and height.

Credit goes to Worst and SR69MM-JC for solving this while I was slaving away at work yesterday. Also, thanks to all those who provided some input. Hopefully someone may find this code useful for other applications.