Jump to content


Photo

Hexagon Pathfinding 1.0


  • Please log in to reply
9 replies to this topic

#1 Gamer3D

Gamer3D

    Human* me = this;

  • GMC Member
  • 1819 posts
  • Version:GM:Studio

Posted 03 August 2008 - 10:41 PM

Many games use a set of square tiles for pathfinding and grid snapping. This grid is not a very good approximation of real life, and can be replaced with a hexagonal grid which may be more visually appealing or help gameplay. The main problem with this is that some easy pathfinding functions in GM, etc. only support square tiles.

With this in mind, and considering making a tactics game using hexagonal tiles, I created a DLL for pathfinding in a hexagonal grid. The basics were done in three days. In another two days, I mananged to improve it to the point where I cannot improve its speed any more without significant effort.

Features include, but are not limited to:
  • Up to 64 grids that can each have separate paths, costs, and impassable regions.
  • Impassable and costly tiles. Note: Cost currently must be 1 or above.
  • Path and node list creation for path output, in addition to direct access.
  • If grid_optimize has been called, no attempt will be made to find a path to an inaccessible spot.
  • Fast. 400 FPS in worst case scenario, 840 in average, and 7700 in best case.

Screenshot:
Posted Image

This extension includes the :mellow: test program as an example.
Download from Mediafire

Suggestions are VERY welcome.

Edited by Gamer3D, 12 June 2012 - 07:11 PM.

  • 0

#2 _175023

_175023

    GMC Member

  • New Member
  • 46 posts

Posted 06 November 2010 - 01:54 AM

Great code, I'm working it out. Can you explain a bit more about what the keys do? M N R T D ?
Thanks.


Many games use a set of square tiles for pathfinding and grid snapping. This grid is not a very good approximation of real life, and can be replaced with a hexagonal grid which may be more visually appealing or help gameplay. The main problem with this is that some easy pathfinding functions in GM, etc. only support square tiles.


Edited by _175023, 06 November 2010 - 01:55 AM.

  • 0

#3 Drara

Drara

    GMC Member

  • GMC Member
  • 325 posts

Posted 06 November 2010 - 12:53 PM

Realy realy nice. The speed is awesome and it is very effectiv too.
It deserves a lot more atttention than it gets. But the example is far too complicated and comments wouldn't be bad.

I'll very probably use it and give you credits.

An advance could be multicell ways.
That means that you set the object to need a square of 4 cells or a circle of 7 cells. I don't know whether this is easy to realize, but it would be very great for rts to have larger units. Using grids with larger cells isn't always an option.

Another thing, could you release a scripts version. Because I would like to write directly the external_call funktion for recieving points in step events. The calling through a script slows everything completly unnecesarry a bit down.
Even executing an empty script takes time.

Edited by Drara, 06 November 2010 - 12:58 PM.

  • 0

#4 Gamer3D

Gamer3D

    Human* me = this;

  • GMC Member
  • 1819 posts
  • Version:GM:Studio

Posted 24 November 2010 - 02:18 AM

Can you explain a bit more about what the keys do? M N R T D ?

M - Destroy the pathfinding grid.
N - Create a new pathfinding grid.
R - Resize the pathfinding grid (at random in the example)
T - Toggles testing mode (default on). Turn it off to see just how fast the extension runs without graphical displays.
D - This is part of an object I forgot to remove.

Also, hold B while placing a tile to place one with higher cost (i.e. lower movement speed).


Realy realy nice. The speed is awesome and it is very effectiv too.
It deserves a lot more atttention than it gets. But the example is far too complicated and comments wouldn't be bad.

Wow, It's been years since I posted this. I thought it simply faded into obscurity.

An advance could be multicell ways.
That means that you set the object to need a square of 4 cells or a circle of 7 cells. I don't know whether this is easy to realize, but it would be very great for rts to have larger units. Using grids with larger cells isn't always an option.

If I ever re-make this in C++, I'll keep this in mind.

Another thing, could you release a scripts version. Because I would like to write directly the external_call funktion for recieving points in step events. The calling through a script slows everything completly unnecesarry a bit down.
Even executing an empty script takes time.

I don't have time right now to make a script version, but if you want the DLL calls, you can get them from the extension source: here (GED file)
  • 0

#5 Drara

Drara

    GMC Member

  • GMC Member
  • 325 posts

Posted 24 November 2010 - 06:31 PM

Thanks, but I can't get the code from the ged. When compiling a ged it wants the gml-files where the code is stored.
Also, this file would be the script version... but it's not included in the source file.
  • 0

#6 Gamer3D

Gamer3D

    Human* me = this;

  • GMC Member
  • 1819 posts
  • Version:GM:Studio

Posted 26 November 2010 - 05:11 AM

Thanks, but I can't get the code from the ged. When compiling a ged it wants the gml-files where the code is stored.
Also, this file would be the script version... but it's not included in the source file.


Oh. Thought you meant the DLL function names.

Put this in a .gml file:

#define hex_path_make_path
if !path_exists(argument1)
    show_error('Specified path does not exist.', false);
else
{
    path_clear_points(argument1);
    path_add_point(argument1, hex_path_node_x(argument0), hex_path_node_y(argument0), 100 / max(0.0001, hex_path_node_cost(argument0)));
    while hex_path_node_next(argument0)
        path_add_point(argument1, hex_path_node_x(argument0), hex_path_node_y(argument0), 100 / max(0.0001, hex_path_node_cost(argument0)));
    path_set_closed(argument1, false);
    return true;
}
return false;
#define hex_path_make_list
var result;
result = ds_list_create();
ds_list_add(result, hex_path_node_x(argument0));
ds_list_add(result, hex_path_node_y(argument0));
while hex_path_node_next(argument0) {
    ds_list_add(result, hex_path_node_x(argument0));
    ds_list_add(result, hex_path_node_y(argument0));
}
return result;

  • 0

#7 Drara

Drara

    GMC Member

  • GMC Member
  • 325 posts

Posted 26 November 2010 - 04:00 PM

Ah sorry. I forgot how the extensionmaker works. I found the dll-functions names I searched.

But where is the dll? I think it isn't included in the ged-file... Or is there a possibliyty to acces it when I use the extension?

Edited by Drara, 26 November 2010 - 04:01 PM.

  • 0

#8 Gamer3D

Gamer3D

    Human* me = this;

  • GMC Member
  • 1819 posts
  • Version:GM:Studio

Posted 26 November 2010 - 08:56 PM

Ah sorry. I forgot how the extensionmaker works. I found the dll-functions names I searched.

But where is the dll? I think it isn't included in the ged-file... Or is there a possibliyty to acces it when I use the extension?


Oh yeah... Sorry about that. It's been years since I used the extension maker.

It's been long enough that I might as well make it open-source anyway, so here you go:
Extension (Open Source + Binaries)

Edited by Gamer3D, 12 June 2012 - 07:11 PM.

  • 1

#9 kaibil

kaibil

    GMC Member

  • GMC Member
  • 119 posts
  • Version:GM8

Posted 08 July 2012 - 07:10 PM

Error installing extension... :/
  • 0

#10 freko

freko

    The Professional

  • GMC Member
  • 504 posts
  • Version:GM8

Posted 13 July 2012 - 09:39 AM

I found this very useful. Keep up the good work :)
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users