# [MUD-Dev] Breaking down the walls

David B. Held dheld at codelogicconsulting.com
Thu Jun 13 09:42:46 New Zealand Standard Time 2002

```From: "Brian Lindahl" <lindahlb at hotmail.com>

> This is the basic idea of my regional design. Every terrain, area,
> building's boundaries can be described by the set of polygons
> where another terrain, area, or building ends.

...

> I hope to tie regions to only convex polygons since the operations
> on convex polygons are significantly faster than those of concave,
> but we'll see how it goes.

After trying to create a polygon-based system, I decided that A) it
was much too complex for me to try on a first iteration, and B) it
is potentially very computationally expensive.  Of course, I have
the more ambitious problem of mapping the polygon set over an ASCII
grid, which involves nasty problems like "find the polygon
containing point (x, y)".  When you have to perform this operation
numerous times to "render" a map, you start looking for speed
hacks. ;)

So my speed hack was: don't use unrestricted polygons.  Instead, I
use rectangles.  "Rectangles???" you say?  Yup.  Only instead of
just rectangles, they are really paired triangles forming a
rectangle.  Each corner of the rectangle has its own elevation, and
you specify which orientation the two triangles have.  This has the
effect that you can cover any polygonal shape, but it might require
more than one tile.  To form a diamond, for instance, requires four
tiles.  The upshot is that you now have a rectilinear graph which
vastly simplifies all kinds of space calculations, and provides a
relatively fast way to do coordinate searching and other stuff.  The
constraints allow you to make various optimizing assumptions (like
where to expect connecting tiles, etc.).  The system isn't complete,
or perfect, but it's certainly interesting, and I will need more
time with it to decide whether it works the way I want it to.

Dave

_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev

```