ID:135094
 
After a moderate bit of effort, I produced an implementation of the Bresenham line drawing algorithm which draws lines through the use of the DrawBox() proc.

//Title: Line Drawing Snippet
//Credit to: Spuzzum
//Contributed by: Spuzzum

/*
This is a simple implementation of the Bresenham algorithm in all four quadrants
which draws a line, places a bunch of objects on the screen taking on the form of
that line, then returns a list of those objects.


Two main procs exist:

drawline(atom/source, atom/target, colour=rgb(0,0,0), linetype=/obj, thickness=1)
Draws a line from the midpoint of the tile of the 'source' to the midpoint of the
tile of the 'target'. That line will be coloured according to the 'colour'
variable and will be produced in the form of a series of objs of type 'linetype'.
The 'thickness' variable is presently unimplemented. In actual fact, this proc
is just a "wrapper" that calls the function below.

drawline_px(x1,y1, x2,y2, colour=rgb(0,0,0), linetype=/obj, thickness=1)
Draws a line from the specified pixel at coordinates 'x1','y1', counting from the
southwesternmost corner of the map, to the specified pixel at coordinates 'x2',
'y2', again counting from the southwesternmost corner of the map. The line will
be coloured according to the 'colour' variable and will be produced in the form
of a series of objs of type 'linetype'. The 'thickness' variable is presently
unimplemented.


The third proc is internal, and should not be called manually:

drawline_pixel(x,y, list/line_tiles, colour, thickness)
Searches through the 'line_tiles' list, then finds or creates a tile which would
encompass the specified pixel coordinates (as specified from the lower left corner
of the map) and draws a single pixel (coloured by 'colour') on that tile. The
'thickness' variable is unimplemented.
*/



line_tile
var/x = 0
var/y = 0
var/icon/tile_icon

New(x, y)
src.x = x; src.y = y


proc/drawline(atom/source, atom/target, colour=rgb(0,0,0), linetype=/obj, thickness=1,
z = source.z)

if(!source) {CRASH("user error -- no source provided"); return}
if(!target) {CRASH("user error -- no target provided"); return}

return drawline_px(
(source.x*32)-16, (source.y*32)-16, (target.x*32)-16, (target.y*32)-16,
colour, linetype, thickness, z)


proc/drawline_px(x1,y1, x2,y2, colour=rgb(0,0,0), linetype=/obj, thickness=1, z=1)
var/list/line_tiles = list()

var/error = 0; var/dx = (x2-x1); var/dy = (y2-y1)
var/x = x1; var/y = y1;

var/x_increment = (dx >= 0) ? 1 : -1; var/y_increment = (dy >= 0) ? 1 : -1

if(dx >= dy)
for(var/i = 1, i <= dx, i++)
drawline_pixel(x, y, line_tiles, colour, thickness)
error += dy
if(error >= dx)
error -= dx
y += y_increment
x += x_increment
else
for(var/i = 1, i <= dy, i++)
drawline_pixel(x, y, line_tiles, colour, thickness)
error += dx
if(error > 0)
error -= dy
x += x_increment
y += y_increment

var/list/objects = list()
for(var/line_tile/tile in line_tiles)
var/atom/O = new linetype(locate(tile.x, tile.y, z))
O.icon = tile.tile_icon
objects += O

return objects


proc/drawline_pixel(x, y, list/line_tiles, colour, thickness=1)
var/line_tile/tile
for(tile in line_tiles)
if(tile.x == (round(x/32)+1) && tile.y == (round(y/32)+1)) break

if(!tile)
tile = new /line_tile(round(x/32)+1, round(y/32)+1)
line_tiles += tile

if(!tile.tile_icon) tile.tile_icon = new /icon('blank.dmi')
tile.tile_icon.DrawBox(colour,(x%32)+1,(y%32)+1)


/*
//Testing code/sample implementation:

turf/Click()
..()
var/list/objects = drawline(usr, src, "#FF0000")
spawn(100)
for(var/obj/O in objects) del(O)
objects.len = 0
*/

(Sorry for the lack of comments.)

There are notable amounts of inefficiency in my code. For instance, it searches through the line_tiles list for every single pixel. (A better system would use a matrix of dimensions [min(x1,x2)] by [max(y1,y2)], eliminating the searching operation and utilising a mere table lookup.) It also has no provisions to cache the results.

However, as it stands, replacing the list search with a table lookup wouldn't improve matters much.

A simple line drawn from locate(1,1,1) on my map to locate(14,14,1) requires 448 pixels to be drawn. Using the code above, that takes a whopping 0.11 seconds of real time (on my 1.7 GHz Athlon 2100+) in order to draw the icons and assign them to objs, and presumably several more centiseconds in order to transmit those icons into the client's resource file and then draw them onto the screen. With more efficient code, I suspect it could be reduced to two-thirds of that, but even at that rate, it is still extraordinarily processor-intensive.

If vector lines could be implemented -- a single transmission to the client, and then the client handles the drawing on the client end -- line drawing would become feasible.

So could we or will we see vector-based lines, and perhaps other polygons, sometime soon? Without it, any line drawing effects -- such as for laser beams and other graphical niceties -- will remain entirely impractical.
If BYOND ever recieves its OpenGL support, that would not only be possible, but also -relatively- workable. Maybe we should poke the powers above to get working on it.

splatty
So could we or will we see vector-based lines, and perhaps other polygons, sometime soon? Without it, any line drawing effects -- such as for laser beams and other graphical niceties -- will remain entirely impractical.

Not really just pregenerate all the possible lines you can have on a single tile and just build your lines with these tiles. You only need to pre-generate 1024 tiles as you just build a line from the point (1,1) to every other point on the tile then to get any other line you can just shift your parts around and flip to get any other combination. Though you probably want to just pregen the flipped lines too so you can get every combination by using pixel offsets so you don't need to dynamiclly create any new icons at runtime.

For one of the previous contests I was planning on doing an asteroids clone but aside from the line drawing functions I never got much farther :P.
In response to splattergnome
splattergnome wrote:
If BYOND ever recieves its OpenGL support, that would not only be possible, but also -relatively- workable. Maybe we should poke the powers above to get working on it.

splatty

Don't forget the Linux GUI that can be made, Not that I care much for linix, But those in the linux camp will love it :P
In response to Xzar
And an OSX gui!