costs.qc File Reference

#include "costs.qh"

Include dependency graph for costs.qc:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
float	pathlib_g_euclidean (entity parent, vector to, float static_cost)
float	pathlib_g_euclidean_water (entity parent, vector to, float static_cost)
float	pathlib_g_static (entity parent, vector to, float static_cost)
float	pathlib_g_static_water (entity parent, vector to, float static_cost)
float	pathlib_h_diagonal (vector a, vector b)
	This heuristic consider both straight and diagonal moves to have the same cost. More...
float	pathlib_h_diagonal2 (vector a, vector b)
	This heuristic consider both straight and diagonal moves, but has a separate cost for diagonal moves. More...
float	pathlib_h_diagonal2sdp (vector preprev, vector prev, vector point, vector end)
	This heuristic consider both straight and diagonal moves, But has a separate cost for diagonal moves. More...
float	pathlib_h_diagonal3 (vector a, vector b)
float	pathlib_h_euclidean (vector a, vector b)
	This heuristic only considers the straight line distance. More...
float	pathlib_h_manhattan (vector a, vector b)
	Manhattan heuristic means we expect to move up, down left or right No diagonal moves expected. More...

Function Documentation

pathlib_g_euclidean()

float pathlib_g_euclidean	(	entity	parent,
		vector	to,
		float	static_cost
	)

Definition at line 16 of file costs.qc.

References vlen().

{
    return parent.pathlib_node_g + vlen(parent.origin - to);
}

Here is the call graph for this function:

pathlib_g_euclidean_water()

float pathlib_g_euclidean_water	(	entity	parent,
		vector	to,
		float	static_cost
	)

Definition at line 21 of file costs.qc.

References inwater, pathlib_movecost_waterfactor, and vlen().

Referenced by pathlib_astar().

{
    if(inwater(to))
        return parent.pathlib_node_g + vlen(parent.origin - to) * pathlib_movecost_waterfactor;
    else
        return parent.pathlib_node_g + vlen(parent.origin - to);
}

Here is the call graph for this function:

Here is the caller graph for this function:

pathlib_g_static()

float pathlib_g_static	(	entity	parent,
		vector	to,
		float	static_cost
	)

Definition at line 3 of file costs.qc.

{
    return parent.pathlib_node_g + static_cost;
}

pathlib_g_static_water()

float pathlib_g_static_water	(	entity	parent,
		vector	to,
		float	static_cost
	)

Definition at line 8 of file costs.qc.

References inwater, and pathlib_movecost_waterfactor.

{
    if(inwater(to))
        return parent.pathlib_node_g + static_cost * pathlib_movecost_waterfactor;
    else
        return parent.pathlib_node_g + static_cost;
}

pathlib_h_diagonal()

float pathlib_h_diagonal	(	vector	a,
		vector	b
	)

This heuristic consider both straight and diagonal moves to have the same cost.

Definition at line 49 of file costs.qc.

References fabs(), max(), and pathlib_movecost.

Referenced by pathlib_astar().

{
    //h(n) = D * max(abs(n.x-goal.x), abs(n.y-goal.y))

    float hx = fabs(a.x - b.x);
    float hy = fabs(a.y - b.y);
    float h = pathlib_movecost * max(hx, hy);

    return h;
}

Here is the call graph for this function:

Here is the caller graph for this function:

pathlib_h_diagonal2()

float pathlib_h_diagonal2	(	vector	a,
		vector	b
	)

This heuristic consider both straight and diagonal moves, but has a separate cost for diagonal moves.

Definition at line 74 of file costs.qc.

References fabs(), min(), pathlib_movecost, and pathlib_movecost_diag.

{
    /*
    h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))
    h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
    h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))
    */

    float hx = fabs(a.x - b.x);
    float hy = fabs(a.y - b.y);

    float h_diag = min(hx,hy);
    float h_str = hx + hy;

    float h =  pathlib_movecost_diag * h_diag;
    h += pathlib_movecost * (h_str - 2 * h_diag);

    return h;
}

Here is the call graph for this function:

pathlib_h_diagonal2sdp()

float pathlib_h_diagonal2sdp	(	vector	preprev,
		vector	prev,
		vector	point,
		vector	end
	)

This heuristic consider both straight and diagonal moves, But has a separate cost for diagonal moves.

Definition at line 98 of file costs.qc.

References fabs(), normalize(), pathlib_movecost, pathlib_movecost_diag, vector(), and vlen().

{
    //h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))
    //h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
    //h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))

    float hx = fabs(point.x - end.x);
    float hy = fabs(point.y - end.y);
    float hz = fabs(point.z - end.z);

    float h_diag = min3(hx,hy,hz);
    float h_str = hx + hy + hz;

    float h =  pathlib_movecost_diag * h_diag;
    h += pathlib_movecost * (h_str - 2 * h_diag);

    vector d1 = normalize(preprev - point);
    vector d2 = normalize(prev    - point);
    float m = vlen(d1 - d2);

    return h * m;
}

Here is the call graph for this function:

pathlib_h_diagonal3()

float pathlib_h_diagonal3	(	vector	a,
		vector	b
	)

Definition at line 122 of file costs.qc.

References fabs(), pathlib_movecost, and pathlib_movecost_diag.

{
    float hx = fabs(a.x - b.x);
    float hy = fabs(a.y - b.y);
    float hz = fabs(a.z - b.z);

    float h_diag = min3(hx,hy,hz);
    float h_str = hx + hy + hz;

    float h =  pathlib_movecost_diag * h_diag;
    h += pathlib_movecost * (h_str - 2 * h_diag);

    return h;
}

Here is the call graph for this function:

pathlib_h_euclidean()

float pathlib_h_euclidean	(	vector	a,
		vector	b
	)

This heuristic only considers the straight line distance.

Usually means a lower H then G, resulting in A* spreading more (and running slower).

Definition at line 65 of file costs.qc.

References vlen().

{
    return vlen(a - b);
}

Here is the call graph for this function:

pathlib_h_manhattan()

float pathlib_h_manhattan	(	vector	a,
		vector	b
	)

Manhattan heuristic means we expect to move up, down left or right No diagonal moves expected.

(like moving between city blocks)

Definition at line 34 of file costs.qc.

References fabs(), and pathlib_gridsize.

{
    //h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))

    float h  = fabs(a.x - b.x);
    h += fabs(a.y - b.y);
    h *= pathlib_gridsize;

    return h;
}

Here is the call graph for this function: