flauwekeul/honeycomb

understanding the run and hexes methods

simon368 opened this issue ยท 7 comments

Hello @flauwekeul,

First, thank you for working on a new version of your library, it actually gave me the motivation to retake an old project.
I know the v4 is still in early stage but you provided some examples and the traversers are very promising.

So, I have a grid manager where I instanciate a grid using this.grid = new Grid(...).each(hex => render(hex)).run(), no big deal it works perfectly. Then, I want to access some of the hexes to change some custom properties defined during render, so I use a traverser (I've made a circular traverser where you define a range from a center hex), then I do const hexes = this.grid.traverser(...).hexes(), the hexes are here but the first each method is called again, rendering my hexes a second time. const hexes = []; this.grid.traverser(...).each(hex => hexes.push(hex)).run() produces the same result.

I understand the idea of stateful grid and I feel like I should use a stateless grid for some operations, but then this.grid.getHex(coordinates) wont be available so I still need a stateful one, right?

Anyway, I have a lot of fun experimenting with it. Here are some fix/features that could really help me out:

  • hexagon grid shape (using a circular traverser by default?)
  • traversing out of store hexes should not mess with the path
  • A* algorithm with the ability to filter out the non traversable hexes

I know some of them are already in the backlog but you also asked for priorities so these are mine.
I know you're taking a new job so if I can contribute in a way, let me know!

A* algorithm can be perfectly used from here:

https://github.com/bgrins/javascript-astar

with slight modification e.g.

Graph.prototype.neighbors = function(node) {
  var ret = [];
  var x = node.x;
  var y = node.y;
  var grid = this.grid;

  // West
  if (grid[x - 1] && grid[x - 1][y]) {
    ret.push(grid[x - 1][y]);
  }

  // East
  if (grid[x + 1] && grid[x + 1][y]) {
    ret.push(grid[x + 1][y]);
  }

  // South
  if (grid[x] && grid[x][y - 1]) {
    ret.push(grid[x][y - 1]);
  }

  // North
  if (grid[x] && grid[x][y + 1]) {
    ret.push(grid[x][y + 1]);
  }

// two cases added below
  // SouthEast
  if (grid[x+1] && grid[x+1][y - 1]) {
    ret.push(grid[x+1][y - 1]);
  }

  // NorthWest
  if (grid[x-1] && grid[x-1][y + 1]) {
    ret.push(grid[x-1][y + 1]);
  }

  if (this.diagonal) {

that you can manage quickly to use (diagonal movement checks below those displayed in the code above are non-relevant for a hex grid). And with the help of svg.js you can create pages like this (cannot share code, it was paid for):

pathfinding-javascript-console-cIds

We really should be grateful for the great library that cannot have all what we need - but it's getting close!

Thanks for trying v4!

the hexes are here but the first each method is called again, rendering my hexes a second time

That shouldn't happen ๐Ÿค” Are you using the latest alpha (4.0.0-alpha.3)? Could you show me some more code?

I understand the idea of stateful grid and I feel like I should use a stateless grid for some operations, but then this.grid.getHex(coordinates) wont be available so I still need a stateful one, right?

You can use getHex() on a stateless grid. The only difference between a stateful and stateless grid is that the latter doesn't add hexes to its store when created. My advice is to use a stateless grid by default. Only if you want to confine your grid to a limited number of hexes and want easy ways to check if you're "crossing your borders", it's better to use a stateful grid. At least, that's the idea.

Yesterday I happened to add a ring() traverser (I just pushed it to the next branch, but haven't released it in a new alpha yet). This commit message and changes should hopefully give you enough information on how to use it. I'll probably add a spiral() traverser later that somehow repeats the ring() traverser to create a hexagon. I tried adding an example here for you to create your own hexagon, but I realised it's not that easy yet. I may make a breaking change in ring() to make it more intuitive to create a spiral.

traversing out of store hexes should not mess with the path

Could you clarify what you mean with this?

A* algorithm with the ability to filter out the non traversable hexes

I have an A* traverser on the backlog ๐Ÿ˜. However, filtering out hexes can already be done with grid.filter(). What do you mean with "non traversable hexes"?

Thanks for your comments. I was about to start using the pathfinder so the project you've shared will come very handy.

Are you using the latest alpha (4.0.0-alpha.3)? Could you show me some more code?

I do, I switched to a stateless grid for this operation but I kept a stateful one since I want to preserve the hexes properties, I've added. So I need to call getHex method on the stateful grid passing the stateless hex as parameter. I'll try again and see if I can reproduce.

Yesterday I happened to add a ring() traverser

We were working on the same feature then, I found it difficult to not have overlap when generating the ring and hexagon shapes. I feel like the at and start method could have a different behaviour, at could mean start here but don't include it. Anyway, I had a lot of fun experimenting with the grid. I've seen your code and now I am less eager to show you mine. ๐Ÿ˜„

Could you clarify what you mean with this?

I was late and I tried to create shapes using multiple hexes corners' coordinates and it would fail but I think it was because I was still using a stateful grid and the hexes I was trying to access were not in store.

What do you mean with "non traversable hexes"?

I was refering to a business rule that you would have on your extended Hex object, which would be used to indicate that an hex can be crossed (e.g. .filter(hex => hex.accessible)).

Thank again for your work and help. I look forward for alpha.4 and the incoming refactoring using your clean methods!

We were working on the same feature then, I found it difficult to not have overlap when generating the ring and hexagon shapes.

I had exactly the same experience. And like you said: there are problems with hexes overlapping when combining traversers.

Traversers can be "chained" by putting them in an array, the next traverser continues where the previous traverser left off. This is done by passing a "cursor" hex between each chained traverser internally. This cursor hex is already traversed by the first traverser, so the next should't also traverse it. I thought about this earlier in the project, but forgot about it along the way and now some traversers produce duplicate hexes when chained.

So, I should make it more explicit and came up with this "rule" all traversers should adhere to: by default, a traverser never traverses the cursor hex. This poses a problem when traversing for the first time, e.g. when creating a grid:

// if the above rule is implemented, this would create a 2x2 grid with the first hex missing (so actually a 1x2 grid):
new Grid(hexPrototype, rectangle({ width: 2, height: 2 }))

To fix this, traversers should be configured that they include the first hex. And it would also be convenient if they can start at certain coordinates instead of continue where the previous traverser left off. I got inspired by your comment:

I feel like the at and start method could have a different behaviour, at could mean start here but don't include it.

Instead of the current at() traverser (that's aliased to start()), I'm planning to give all traversers an optional start and at option that does what you describe: at makes the traverser start at those coordinates but doesn't include those coordinates and start makes the traverser start at those coordinates and includes those coordinates. I think with this, there's no need for a separate at() and start() traverser (with similar behaviour). Okay, maybe something like add() that adds 1 or more coordinates (similar to the current at() traverser).

I hope it's clear what I mean. What do you think?

I really like it, I'm glad we had similar thoughts on this use case. I also think it's important to keep the feature and rename it to add() would make it clearer, especially if it's possible to pass multiple hexes' coordinates.

As for the pre-made grid shapes, they should indeed be as comprehensible as possible for newcomers.

I look forward to test out these new changes!

I just released alpha.4. It contains a ring() and spiral() traverser and I've tried to fix the duplicate hexes that chaining traversers caused. I'm looking forward to your opinion.

Have gotten around to try the new alpha (alpha.5 in the meantime)?