Here is nothing to say. Everything was clearly described
here.
Here is jus my code in haxe implementing GBVF pathfinding class.
package com.nailedgames;
import flash.geom.Point;
typedef PathTile = {
var x:Int;
var y:Int;
var step:Int;
}
class GBVF_pathfinding
{
private var _tile_width:Int;
private var _tile_height:Int;
private var _field_width:Int;
private var _field_height:Int;
private var _field_wtiles:Int;
private var _field_htiles:Int;
private var _distances:Array<Int>;
private var _vectors:Array<Point>;
public var vectors(get,null):Array<Point>;
public function new()
{
}
function get_vectors():Array<Point>
{
return _vectors;
}
public function Init(tile_width:Int, tile_height:Int, field_width:Int, field_height:Int)
{
_tile_width = tile_width;
_tile_height = tile_height;
_field_width = field_width;
_field_height = field_height;
_field_wtiles = Std.int(field_width/tile_width);
_field_htiles = Std.int(field_height/tile_height);
_distances = new Array();
for(i in 0..._field_htiles)
for(j in 0..._field_wtiles)
_distances.push(-1);
}
public function Calculate_field(walls_map:Array<Int>, x_block:Int, y_block:Int):Array<Point>
{
for(i in 0..._distances.length)
if(walls_map[i] == 1)
_distances[i] = -3;
else
_distances[i] = -1;
Mark_tiles([{x:x_block, y:y_block, step:0}]);
return _vectors;
}
private function Mark_tiles(points:Array<Pathtile>):Void
{
if(Lambda.empty(points))
return;
var neighbours:Array<Pathtile> = new Array<Pathtile>();
for(point in points)
{
_distances[point.x + point.y*_field_wtiles] = point.step;
if(point.x > 0)
{
if(_distances[(point.x-1) + point.y*_field_wtiles] == -1)
{
neighbours.push({x:point.x-1, y:point.y, step:point.step+1});
_distances[(point.x-1) + point.y*_field_wtiles] = -2;
}
}
if(point.x < (_field_wtiles-1))
{
if(_distances[(point.x+1) + point.y*_field_wtiles] == -1)
{
neighbours.push({x:point.x+1, y:point.y, step:point.step+1});
_distances[(point.x+1) + point.y*_field_wtiles] = -2;
}
}
if(point.y > 0)
{
if(_distances[point.x + (point.y-1)*_field_wtiles] == -1)
{
neighbours.push({x:point.x, y:point.y-1, step:point.step+1});
_distances[point.x + (point.y-1)*_field_wtiles] = -2;
}
}
if(point.y < (_field_htiles-1))
{
if(_distances[point.x + (point.y+1)*_field_wtiles] == -1)
{
neighbours.push({x:point.x, y:point.y+1, step:point.step+1});
_distances[point.x + (point.y+1)*_field_wtiles] = -2;
}
}
}
Mark_tiles(neighbours);
Assign_vectors();
}
private function Assign_vectors():Void
{
_vectors = new Array<Point>();
for(y_tile in 0..._field_htiles)
{
for(x_tile in 0..._field_wtiles)
{
if(_distances[x_tile + y_tile*_field_wtiles] > 0)
{
var left_dist:Int = _distances[x_tile + y_tile*_field_wtiles]+1;
var right_dist:Int = _distances[x_tile + y_tile*_field_wtiles]+1;
var up_dist:Int = _distances[x_tile + y_tile*_field_wtiles]+1;
var down_dist:Int = _distances[x_tile + y_tile*_field_wtiles]+1;
if((x_tile > 0) && (_distances[(x_tile-1) + y_tile*_field_wtiles] >= 0))
left_dist = _distances[(x_tile-1) + y_tile*_field_wtiles];
if((x_tile < (_field_wtiles-1)) && (_distances[(x_tile+1) + y_tile*_field_wtiles] >= 0))
right_dist = _distances[(x_tile+1) + y_tile*_field_wtiles];
if((y_tile > 0) && (_distances[x_tile + (y_tile-1)*_field_wtiles] >= 0))
up_dist = _distances[x_tile + (y_tile-1)*_field_wtiles];
if((y_tile < (_field_htiles-1)) && (_distances[x_tile + (y_tile+1)*_field_wtiles] >= 0))
down_dist = _distances[x_tile + (y_tile+1)*_field_wtiles];
_vectors.push(new Point(
left_dist - right_dist,
up_dist - down_dist));
}else{
_vectors.push(new Point(0,0));
}
}
}
}
}
Here is usage example:
var tile_width:Int = 40;
var tile_height:Int = 40;
var field_width:Int = 800;
var field_height:Int = 600;
gbvf = new GBVF_pathfinding();
walls_map = [
0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,
0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,0,0,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,
];
gbvf.Init(tile_width, tile_height, field_width, field_height);
var vectors:Array<Point> = gbvf.Calculate_field(walls_map, x_block, y_block);
As a result you will have array of vectors coordinates relative to the center of tiles.