Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

When working on a game, I developed a database that used X/Y coordinates, roughly as:

CREATE TABLE Map
(
    MapId INT IDENTITY PRIMARY KEY,
    X INT NOT NULL,
    Y INT NOT NULL,
    North INT FOREIGN KEY REFERENCES Map(MapId),
    South INT FOREIGN KEY REFERENCES Map(MapId),
    East INT FOREIGN KEY REFERENCES Map(MapId),
    West INT FOREIGN KEY REFERENCES Map(MapId)
);

(I'm not at my editor, so that may have syntax errors.)

I then implemented the path searching algorithm (A*, specifically) inside a stored procedure.

  1. Is there a better way to implement this coordinates system?

  2. I had implemented it in SQL Server, since that is what I had on hand and what I was familiar with. Is there anything in another database system that would've simplified this problem?

It may make a difference to know that this, being a game, is strictly a grid system. That may simplify (or complicate) the problem.

Edit:

Some sample data:

map_id      x           y           north       east        south       west
----------- ----------- ----------- ----------- ----------- ----------- -----------
20          502         501         26          33          21          18
21          502         502         20          22          87          19
22          503         502         33          23          88          21
share|improve this question
    
Are the North, South, East, and West columns supposed to reference the nearest map locations in those directions? –  Nick Chammas Aug 16 '11 at 14:47
    
Right. It was a self-referencing table so that any location could have four directions of exit (just a standard grid). I'll throw some sample data up there. –  Richard Aug 16 '11 at 14:50

1 Answer 1

up vote 2 down vote accepted

If the game area is strictly static, then my preference would be to use the coordinates as the primary key.

On postgres, I'd probably do that using a composite type. I don't think there is a direct equivalent in SQL Server - hopefully someone will correct me if I'm wrong.

Whether this will simplify the problem or not depends on how exactly you have implemented your searching algorithm - can you post more details on that?

share|improve this answer
1  
I could post the A* algorithm, but realistically, it would be easier to rewrite the algorithm to fit the design rather than the other way around. Also, when I designed this, I never thought about solely relying on the x/y coordinates. That's not a bad idea at all. You could use <current X Location> - 1 to move West instead of having strange linkage. +1 from me. –  Richard Aug 16 '11 at 12:00
    
@Richard - wouldn't be an overkill to compute the 4 neighbors all the time when your character moves on the map? Wouldn't it be better, as Jack suggested, to see the neighbors by using on the fly computations, as I think you'd need less times to see the neighbors of the current spot then to compute 4 neighbors for every single move. –  Marian Aug 16 '11 at 22:35
    
Yes and no. The A* search algorithm is surprisingly efficient. You don't actually calculate all four exit paths when you plan a route. You just calculate the path(s) that will most likely get you there. If you're moving straight West, for example, you will only check the squares that are straight West. But if you're moving exactly NorthWest, then you'll need to consider which direction to take for the grid. (North then west or West then north). See here. –  Richard Aug 17 '11 at 12:22
    
or here :) –  Jack Douglas Aug 17 '11 at 12:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.