Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

> [EV] How do you prevent backtracking in this case? Going 2-8-10-12-6?
Sorry, I have not explained it correctly. I have this algorithm nearly  
independent from the game data and the connectivity graph used in the  
route search is different from the tile description itself (and while  
explaining it I've mixed them together). The "outer" vertices (#1-#6) are  
 from the tile definition and don't appear in the connectivity graph at  
all. So when Y tile connectivity is converted into the abstract graph for  
route calculation, there will be 5 edges: (2'-8,8-10,10-4',6'-12,12-10).
2', 4' and 6' are vertices that are in the adjacent hexes (such that for  
example, 4' is the same vertex as vertex 7 of the hex just below this  
one). Backtracking is prevented by allowing only one edge from any  
particular tile to be used consequently unless it starts or ends in the  
center.

I also should notice that all these vertices are purely abstract, there is  
no data corresponding to them in the program. Only particular vertices  
(such as with city or town) get their own data (I call them nodes).


On Sun, 21 Mar 2010 09:05:28 -0600, Erik Vos <eri...@xs...> wrote:

> OK, I see you have already though about route determination.
>
> -----Original Message-----
> From: alexti [mailto:al...@sh...]
> Let's say we have a hex
> oriented so that one side is facing north, another south and the other 4
> NW, SW, NE and SE. For each hex there will be 13 vertices. One in the
> center (#0), 6 vertices each in the middle of the hex edge (#1-#6, #1 is
> North, counting clockwise) and 6 more in the middle of the line  
> connecting
> each of vertices #1-#6 to the center. Vertices #1-#6 will be shared with
> other adjacent hexes. Let's say we have green Y tile (two gently curving
> tracks from S to NW and from S to NE). Connectivity graph for such tile
> will be (2-8,8-10,10-4,6-12,12-10). 10-4 edge represents the bottom of  
> "Y"
> and this ensures that only one of the track segments on this tile can be
> used.
>
> [EV] How do you prevent backtracking in this case? Going 2-8-10-12-6?
>
> -----Original Message-----
> From: Stefan Frey [mailto:ste...@we...]
> - I prefer your definition of the graph to the one in tiles.xml  
> (inherited
> from the tiledesigner) as you only have to count edges and you do not  
> have
> to
> consider that you are not allowed to visit the same side (a node/vertex  
> in
> Rails) twice. Rails defines tile 25 (the green Y) with two edges that  
> both
> start from the same side  (see tiles.xml), but only one of each edge can  
> be
> used per revenue turn.
>
> [EV] I would rather think that the current Rails Tile definition would be
> easier to use, as the only two requirements to make it work are:
> - each edge (and station) may be visited only once,
> - return from an edge is never allowed.
> See my question above: it seems harder to do with the extra vertexes, as  
> it
> doen't seem to be clear what would prevent going 8-12-10. Or is that  
> somehow
> built into the vertex #7-12 properties?
>
> Erik.
>
>
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/