//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.
splatty