scummvm-cursorfix/engines/ags/engine/ac/route_finder_jps.h

/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include "common/std/queue.h"
#include "common/std/vector.h"
#include "common/std/algorithm.h"
#include "common/std/functional.h"
#include "common/std/xutility.h"

// Not all platforms define INFINITY
#ifndef INFINITY
#define INFINITY   ((float)(1e+300 * 1e+300)) // This must overflow
#endif

namespace AGS3 {

// TODO: this could be cleaned up/simplified ...

// further optimizations possible:
//    - forward refinement should use binary search

class Navigation {
public:
	Navigation();

	void Resize(int width, int height);

	enum NavResult {
		// unreachable
		NAV_UNREACHABLE,
		// straight line exists
		NAV_STRAIGHT,
		// path used
		NAV_PATH
	};

	// ncpath = navpoint-compressed path
	// opath = path composed of individual grid elements
	NavResult NavigateRefined(int sx, int sy, int ex, int ey, std::vector<int> &opath,
	                          std::vector<int> &ncpath);

	NavResult Navigate(int sx, int sy, int ex, int ey, std::vector<int> &opath);

	bool TraceLine(int srcx, int srcy, int targx, int targy, int &lastValidX, int &lastValidY) const;
	bool TraceLine(int srcx, int srcy, int targx, int targy, std::vector<int> *rpath = nullptr) const;

	inline void SetMapRow(int y, const unsigned char *row) {
		map[y] = row;
	}

	static int PackSquare(int x, int y);
	static void UnpackSquare(int sq, int &x, int &y);

private:
	// priority queue entry
	struct Entry {
		float cost;
		int index;

		inline Entry() {}

		inline Entry(float ncost, int nindex)
			: cost(ncost)
			, index(nindex) {
		}

		inline bool operator <(const Entry &b) const {
			return cost < b.cost;
		}

		inline bool operator >(const Entry &b) const {
			return cost > b.cost;
		}
	};

	int mapWidth;
	int mapHeight;
	std::vector<const unsigned char *> map;

	typedef unsigned short tFrameId;
	typedef int tPrev;

	struct NodeInfo {
		// quantized min distance from origin
		unsigned short dist;
		// frame id (counter to detect new search)
		tFrameId frameId;
		// previous node index (packed, relative to current node)
		tPrev prev;

		inline NodeInfo()
			: dist(0)
			, frameId(0)
			, prev(-1) {
		}
	};

	static const float DIST_SCALE_PACK;
	static const float DIST_SCALE_UNPACK;

	std::vector<NodeInfo> mapNodes;
	tFrameId frameId;

	std::priority_queue<Entry, std::vector<Entry>, Common::Greater<Entry> > pq;

	// temporary buffers:
	mutable std::vector<int> fpath;
	std::vector<int> ncpathIndex;
	std::vector<int> rayPath, orayPath;

	// temps for routing towards unreachable areas
	int cnode;
	int closest;

	// orthogonal only (this should correspond to what AGS is doing)
	bool nodiag;

	bool navLock;

	void IncFrameId();

	// outside map test
	inline bool Outside(int x, int y) const;
	// stronger inside test
	bool Passable(int x, int y) const;
	// plain access, unchecked
	inline bool Walkable(int x, int y) const;

	void AddPruned(int *buf, int &bcount, int x, int y) const;
	bool HasForcedNeighbor(int x, int y, int dx, int dy) const;
	int FindJump(int x, int y, int dx, int dy, int ex, int ey);
	int FindOrthoJump(int x, int y, int dx, int dy, int ex, int ey);

	// neighbor reachable (nodiag only)
	bool Reachable(int x0, int y0, int x1, int y1) const;

	static inline int sign(int n) {
		return n < 0 ? -1 : (n > 0 ? 1 : 0);
	}

	static inline int iabs(int n) {
		return n < 0 ? -n : n;
	}

	static inline int iclamp(int v, int min, int max) {
		return v < min ? min : (v > max ? max : v);
	}

	static inline int ClosestDist(int dx, int dy) {
		return dx * dx + dy * dy;
		// Manhattan?
		//return iabs(dx) + iabs(dy);
	}
};

inline int Navigation::PackSquare(int x, int y) {
	return (y << 16) + x;
}

inline void Navigation::UnpackSquare(int sq, int &x, int &y) {
	y = sq >> 16;
	x = sq & ((1 << 16) - 1);
}

inline bool Navigation::Outside(int x, int y) const {
	return
	    (unsigned)x >= (unsigned)mapWidth ||
	    (unsigned)y >= (unsigned)mapHeight;
}

inline bool Navigation::Walkable(int x, int y) const {
	// invert condition because of AGS
	return map[y][x] != 0;
}

} // namespace AGS3