Author Topic: Generic algorithms for complex data?  (Read 7377 times)

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Generic algorithms for complex data?
« on: June 21, 2016, 09:47:42 AM »
Let's say there is an array class with methods for drawing ellipses, rectangles etc. These routines access unsigned char (or some other simple type) of the array. Now, I've wondered if it's possible to make generic routines in case where you change the array to have items of more complex structs with some member variable of that struct that needs an ellipse routine. How do you write a routine to accept those types? Is it even possible without template/macro madness?

This is a real issue I'm having with Teemu, which has for now used simple arrays for each type of map data (light, fov, etc.) But I've started to combine these into more logical tiles that have a struct with members for that data. Then I noticed I have to write ellipse etc. routines for all different maps and if I have more than one variable it has to be written in the algorithm to choose what variable is changed by that algorithm.

Edit: well, one idea I just had is change the routines to create a list of coordinates (in a shape) which then are processed as a list retrieved from an ellipse routine. It's slower, but... it could work.
« Last Edit: June 21, 2016, 09:51:59 AM by Krice »

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Generic algorithms for complex data?
« Reply #1 on: June 21, 2016, 10:52:48 AM »
It does work. And you can pre-generate different size of ellipses (for example) and offset them to proper location. Then it may be even faster because you don't have to use the algorithm, but only the flattened list of coordinates.

Skullcoder

  • Newcomer
  • Posts: 23
  • Karma: +0/-0
    • View Profile
    • Skullcode
    • Email
Re: Generic algorithms for complex data?
« Reply #2 on: June 21, 2016, 11:45:24 PM »
Pointers are a "simple" type.  Substitute arrays of a simple unsigned char type with arrays of pointers to a complex room struct (or linked list, or whatever), and Bob's your uncle.

"All problems in computer science can be solved by another level of indirection."
- David Wheeler.

"...except for the problem of too many layers of indirection."
- Kevlin Henney

Pointers are a level of indirection.  As are methods for working with 2D data of dynamic raster width in a 1D array.
« Last Edit: June 21, 2016, 11:49:41 PM by Skullcoder »

Cfyz

  • Rogueliker
  • ***
  • Posts: 194
  • Karma: +0/-0
    • View Profile
    • Email
Re: Generic algorithms for complex data?
« Reply #3 on: June 22, 2016, 12:28:14 AM »
You can instruct the routine which member to use. Even without templates.

struct Cell {
    bool light;
    bool fov;
    ...
};

void Calc(Cell* array, bool Cell::*field) {
    ...
    Cell& p = array[j];
    (p.*field) = true;
    ...
}

Calc(cells, &Cell::light);
Calc(cells, &Cell::fov);

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Generic algorithms for complex data?
« Reply #4 on: June 22, 2016, 09:51:04 AM »
What if you want to use other struct than Cell?

reaver

  • Rogueliker
  • ***
  • Posts: 207
  • Karma: +0/-0
    • View Profile
Re: Generic algorithms for complex data?
« Reply #5 on: June 22, 2016, 10:38:46 AM »
Use what you said. A list of 2D coordinates. It's enough to define a shape in a 2D grid. Then you can do with them whatever you want. Templates would replicate code needlessly. Any other crafty stuff just adds unnecessary complexity.

Cfyz

  • Rogueliker
  • ***
  • Posts: 194
  • Karma: +0/-0
    • View Profile
    • Email
Re: Generic algorithms for complex data?
« Reply #6 on: June 22, 2016, 10:52:21 AM »
Quote from: Krice
What if you want to use other struct than Cell?
Then, well...
template<typename T> void Calc(T* array, bool T::*field);
Though precalculating sets of coordinates is okay if you can wrap the code logic around that.


Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Generic algorithms for complex data?
« Reply #7 on: June 22, 2016, 12:52:40 PM »
I like the generic shape idea and it doesn't look that bad, you only need an extra routine to create stuff in the list:

Code: [Select]
void Terrain_Map::Process_Terrain_Shape(Generic_Shape &s, int tile)
{
//create shape from a list of coordinates
for (vector<Coords>::iterator pos=s.points.begin(); pos!=s.points.end(); ++pos)
{
Put_Terrain((*pos), tile);
}
}

void Terrain_Map::Create_Terrain_Ellipse(const Coords &c, int rx, int ry, int tile)
{
Generic_Ellipse e(c, rx, ry);
Process_Terrain_Shape(e, tile);
}

reaver

  • Rogueliker
  • ***
  • Posts: 207
  • Karma: +0/-0
    • View Profile
Re: Generic algorithms for complex data?
« Reply #8 on: June 22, 2016, 01:03:20 PM »
I have something similar but even simpler, the shapes are just a vector of 2D points, you don't need to have a class hierarchy for that (Generic_Whatever). Just have a bunch of functions e.g.
void make_circle(std::vector<point2d>& shape, point2d center, int radius)
void make_rectangle(std::vector<point2d>& shape, point2d lower_left, point2d upper_right)
etc...

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Generic algorithms for complex data?
« Reply #9 on: June 22, 2016, 05:48:16 PM »
Class hierarchy is of course better, because you can have the base class as container for points (which in this case is struct/public access class) with some basic functions and then derived classes for different shapes. The base class looks like this:

Code: [Select]
struct Generic_Shape
{
std::vector<Coords> points;

Generic_Shape() { }

void Add_Point(const Coords &c);
void Add_Point(int x, int y);
};