Line handling improvements.

[HexDecimal]

Copied from this comment: #91 (comment)

Since line drawing is a pretty low-level task most of the code should be moved inline, even in C using C99 inline functions. I haven't gotten used to how to implement these correctly.

For the callback-based functions. The C callbacks need an additional userdata parameter to be useful. C++ should support lambdas as callbacks.

C should have a function that outputs a full array of line indexes to a buffer. C++ might use this function to return a std::vector of line coordinates.

C++ should have a dynamic iterator supporting ranged-based for loops to iterate over line coordinates without a heap buffer.

• C array output.
• C++ forward iterator with range support.
• C++ iterator with custom ranges.
• C++ bidirectional iterator.
• C++ arbitrary iteration.

[HexDecimal]

Ideally C++ should have range and structured binding support, so that you can iterate over a line like this:

for (auto&& [x, y] : tcod::bresenham({start_x, start_y}, {end_x, end_y})) {
  // ...
}

In C there should be an additional option to output the indexes to an array output:

int length = TCOD_bresenham(start_x, start_y, end_x, end_y, 0, NULL);  // TCOD_bresenham(x, y, x2, y2, n, out)
int* indexes = malloc(sizeof(*indexes) * length * 2);
TCOD_bresenham(0, 0, 4, 4, length, indexes);

[sensualcoder]

For the C++ portion, I could add an InputIterator definition to the BresenhamLine class and create a new free function based on the callback one that doesn't take a callback, then the function can return that iterator. The iterator get method can then return the [x, y] structured bindings.

The function definition can be something like inline BresenhamLine::iterator bresenham(std::pair<int, int> from, std::pair<int, int> to);

Edit: Actually, just defining a constructor that takes two std::pair<int, int> and the iterator would work, then you can just do:

for(auto&& [x, y] : tcod::BresenhamLine({0, 0}, {10, 10}))
{
    // do work
}

[HexDecimal]

I think I'll always prefer std::array<int, 2> over std::tuple<int, int> or std::pair<int, int>. std::pair in particular has implementation issues which can mess up compiler optimizations when used (not sure if this is still the case.)

[HexDecimal]

I've made significant changes to the BresenhamLine class. It no longer uses the C functions and can even iterate over a Bresenham line in reverse. It supports clipping the endpoints. It's slightly faster than calling the C function.

Later I'll probably change it so that the iterator functionality is part of the main class instead of a separate internal class. I think the hard parts are already done.

[sensualcoder]

That's awesome, I never would have thought about decomposing the problem like that. Maybe I should brush up on my math a little, since even inverting the Bresenham algorithm seemed a little beyond me.

[HexDecimal]

I quick look at the Wikipedia article on Bresenham explains how the integer version of Bresenham is implemented. It's really just a fancy way of handling a division operation without using real division by keeping track of the fractional remainder manually (the error variable.)

A lot of the algorithm was for handling edge cases with octants, I could represent octants as transform matrices instead of having to implement those edge cases in the algorithm itself, which means I only have to do one octant (the low slope) and that keeps the real implementation simple. At that point it's easy to see how to reverse Bresenham's algorithm. The C++ compiler optimizes out the complexity of the transform matrix since it's generated from a pure inline function. The way the State object is kept in sync with the iterator is also optimized out. So in the end this runs a little faster than the original C call.