behaviour-tree-test/modules/generative_grammar/grammar.cpp

#include "generative_grammar/grammar.h"
#include "core/math/math_funcs.h"
#include "core/object/class_db.h"
#include "core/templates/hash_set.h"
#include "core/variant/typed_array.h"
#include "macros.h"

void Sentence::_bind_methods() {
	BIND_PROPERTY(Variant::VECTOR2I, size);
	BIND_HPROPERTY(Variant::STRING, symbols_string, PROPERTY_HINT_MULTILINE_TEXT);
}

bool Sentence::is_terminal() const {
	for (Symbol c : this->symbols) {
		if (!symbol_is_terminal(c)) {
			return false;
		}
	}
	return true; // no non-terminals in sentence
}

int Sentence::difficulty_at(Vector2i coord) const {
	if (this->difficulty_map_scale <= 0) {
		return -1;
	}
	if (this->read_transposed) {
		int x{ coord.x };
		coord.x = coord.y;
		coord.y = x;
	}
	if (this->read_flip_h) {
		coord.x = this->size.x - (coord.x + 1);
	}
	if (this->read_flip_v) {
		coord.y = this->size.y - (coord.y + 1);
	}
	ERR_FAIL_COND_V_EDMSG(coord.x >= this->size.x, NonTerminals::Invalid, vformat("Sentence::get_at: invalid coordinate x:%d, size.x:%d", coord.x, this->size.x));
	ERR_FAIL_COND_V_EDMSG(coord.y >= this->size.y, NonTerminals::Invalid, vformat("Sentence::get_at: invalid coordinate y:%d size.y:%d", coord.y, this->size.y));
	coord /= this->difficulty_map_scale;
	return difficulty_map.has(coord) ? difficulty_map.get(coord) : -1;
}

Symbol Sentence::get_at(Vector2i coord) const {
	if (this->read_transposed) {
		int x{ coord.x };
		coord.x = coord.y;
		coord.y = x;
	}
	if (this->read_flip_h) {
		coord.x = this->size.x - (coord.x + 1);
	}
	if (this->read_flip_v) {
		coord.y = this->size.y - (coord.y + 1);
	}
	ERR_FAIL_COND_V_EDMSG(coord.x >= this->size.x, NonTerminals::Invalid, vformat("Sentence::get_at: invalid coordinate x:%d, size.x:%d", coord.x, this->size.x));
	ERR_FAIL_COND_V_EDMSG(coord.y >= this->size.y, NonTerminals::Invalid, vformat("Sentence::get_at: invalid coordinate y:%d size.y:%d", coord.y, this->size.y));
	int idx{ coord.x + (coord.y * this->size.x) };
	ERR_FAIL_COND_V_EDMSG(idx >= this->symbols.size(), NonTerminals::Invalid, vformat("Sentence::get_at: invalid coordinate x:%d y:%d idx:%d size:%d,%d len:%d h:%s v:%s t:%s", coord.x, coord.y, idx, this->size.x, this->size.y, this->symbols.size(), this->read_flip_h, this->read_flip_v, this->read_transposed));
	return this->symbols.get(idx);
}

void Sentence::set_at(Vector2i coord, Symbol symbol) {
	ERR_FAIL_COND_EDMSG(coord.x >= this->size.x, vformat("Sentence::get_at: invalid coordinate x:%d, size.x:%d", coord.x, this->size.x));
	ERR_FAIL_COND_EDMSG(coord.y >= this->size.y, vformat("Sentence::get_at: invalid coordinate y:%d size.y:%d", coord.y, this->size.y));
	int idx{ coord.x + (coord.y * this->size.x) };
	ERR_FAIL_COND_EDMSG(idx >= this->symbols.size(), vformat("Sentence::set_at: invalid coordinate x:%d y:%d idx:%d size:%d,%d len:%d", coord.x, coord.y, idx, this->size.x, this->size.y, this->symbols.size()));
	this->symbols.set(idx, symbol);
}

bool Sentence::check_match_at(Vector2i at, Ref<Sentence> pattern) {
	Vector2i const pattern_size{ pattern->get_size() };
	if (at.x < 0 || at.y < 0) {
		return false; // can't match out of negative bounds
	}
	if (at.x + pattern_size.x >= this->size.x || at.y + pattern_size.y >= this->size.y) {
		return false; // can't match, out of positive bounds
	}
	for (Vector2i itr{ 0, 0 }; itr.y < pattern_size.y; ++itr.y) {
		for (; itr.x < pattern_size.x; ++itr.x) {
			Symbol a{ get_at(at + itr) }, b{ pattern->get_at(itr) };
			if (a != b && b != '*' && (b != U'#' || a == U'u')) {
				return false; // difference found
			}
		}
		itr.x = 0;
	}
	return true;
}

void Sentence::write_subsentence(Vector2i at, Ref<Sentence> sentence) {
	for (Vector2i pos{ 0, 0 }; pos.y < sentence->get_size().y; ++pos.y) {
		for (; pos.x < sentence->get_size().x; ++pos.x) {
			Symbol write{ sentence->get_at(pos) };
			if (write != U'*' && write != U'#') { // wildcards don't write
				set_at(at + pos, write);
			}
		}
		pos.x = 0;
	}
}

void Sentence::set_symbols_string(String value) {
	int size{ this->size.x * this->size.y };
	int writer{ 0 };
	for (int reader{ 0 }; writer < size; ++reader) {
		char32_t c{ reader < value.length() ? value.get(reader) : U'u' };
		if (c != U'\n') {
			this->symbols.set(writer, c);
			++writer;
		}
	}
}

String Sentence::get_symbols_string() const {
	String value{};
	for (int i{ 0 }; i < this->symbols.size(); ++i) {
		if (i != 0 && i % this->size.x == 0) {
			value += U'\n';
		}
		value += this->symbols.get(i);
	}
	return value;
}

void Sentence::set_size(Vector2i value) {
	this->size = value;
	this->symbols.clear();
	this->symbols.resize_initialized(this->size.x * this->size.y);
	for (int i{ 0 }; i < this->symbols.size(); ++i) {
		this->symbols.set(i, U'u');
	}
}

Vector2i Sentence::get_size() const {
	return this->read_transposed ? Vector2i{ this->size.y, this->size.x } : this->size;
}

void CompositeRule::_bind_methods() {
	BIND_PROPERTY(Variant::BOOL, random_order);
}

void CompositeRule::_notification(int what) {
	switch (what) {
		case NOTIFICATION_CHILD_ORDER_CHANGED:
			if (!is_ready()) {
				return;
			}
			// fall through
		case NOTIFICATION_READY:
			this->rules.clear();
			for (Variant child : get_children()) {
				if (Rule * rule{ cast_to<Rule>(child) }) {
					this->rules.push_back(rule);
				}
			}
			return;
	}
}

bool CompositeRule::try_apply(Ref<Sentence> sentence) {
	bool any_success{ false };
	if (random_order) {
		Vector<Rule *> rules{};
		rules.append_array(this->rules);
		while (!rules.is_empty()) {
			Vector<Rule *>::Size rand{ Math::rand() % rules.size() };
			Rule *rule{ rules[rand] };
			rules.remove_at(rand);
			any_success |= rule->try_apply(sentence);
		}
	} else {
		for (Rule *rule : this->rules) {
			any_success |= rule->try_apply(sentence);
		}
	}
	return any_success;
}

bool RepeatRuleUntilFailure::try_apply(Ref<Sentence> sentence) {
	ERR_FAIL_COND_V_EDMSG(this->rules.is_empty(), false, "RepeatRuleUntilFailure requires children to run");
	while (super_type::try_apply(sentence)) {
	}
	return true;
}

void ReplaceRule::_bind_methods() {
	BIND_HPROPERTY(Variant::OBJECT, pattern, PROPERTY_HINT_RESOURCE_TYPE, Sentence::get_class_static());
	BIND_HPROPERTY(Variant::DICTIONARY, results_dict, PROPERTY_HINT_DICTIONARY_TYPE, vformat("%s/%s:%s;float", Variant::OBJECT, PROPERTY_HINT_RESOURCE_TYPE, Sentence::get_class_static()));
	BIND_PROPERTY(Variant::INT, match_min_difficulty);
	BIND_PROPERTY(Variant::INT, match_max_difficulty);
	BIND_PROPERTY(Variant::BOOL, deterministic);
}

void ReplaceRule::write_result(Ref<Sentence> to, Vector2i at) {
	Ref<Sentence> result{ this->results[Math::rand() % this->results.size()].first };
	result->read_flip_h = this->pattern->read_flip_h;
	result->read_flip_v = this->pattern->read_flip_v;
	result->read_transposed = this->pattern->read_transposed;
	to->write_subsentence(at, result);
	result->read_flip_h = false;
	result->read_flip_v = false;
	result->read_transposed = false;
}

bool ReplaceRule::try_apply_all(Ref<Sentence> sentence) {
	unsigned total{ 2 * 2 * 2 };
	for (Vector2i pos{ 0, 0 }; pos.y < sentence->get_size().y; ++pos.y) {
		for (; pos.x < sentence->get_size().x; ++pos.x) {
			int difficulty{ sentence->difficulty_at(pos) };
			if ((difficulty > this->match_max_difficulty && this->match_max_difficulty >= 0) || (difficulty < this->match_min_difficulty && this->match_min_difficulty >= 0)) {
				continue;
			}
			unsigned random{ this->deterministic ? 1 : (Math::rand() * 3) % total };
			for (unsigned i{ 0 }; i < total; ++i) {
				this->pattern->read_flip_h = (i * random) & 0b1;
				this->pattern->read_flip_v = (i * random) & 0b10;
				this->pattern->read_transposed = (i * random) & 0b100;
				if (sentence->check_match_at(pos, this->pattern)) {
					write_result(sentence, pos);
					return true;
				}
			}
		}
		pos.x = 0;
	}
	return false;
}

bool ReplaceRule::try_apply(Ref<Sentence> sentence) {
	bool success{ try_apply_all(sentence) };
	this->pattern->read_flip_h = false;
	this->pattern->read_flip_v = false;
	this->pattern->read_transposed = false;
	return success;
}

void ReplaceRule::set_results_dict(Dictionary dict) {
	this->results.clear();
	for (KeyValue<Variant, Variant> var : dict) {
		Ref<Sentence> key{ var.key };
		if (key.is_valid() && var.value.is_num()) {
			float value{ var.value };
			if (key->size != this->pattern->size) {
				key->set_size(this->pattern->size);
			}
			this->results.push_back({ key, value });
		}
	}
}

Dictionary ReplaceRule::get_results_dict() const {
	Dictionary dict;
	for (KeyValue<Ref<Sentence>, float> kvp : this->results) {
		dict[kvp.key] = kvp.value;
	}
	return dict;
}

void ResizeRule::_bind_methods() {
	BIND_PROPERTY(Variant::INT, factor);
}

void ResizeRule::fill_area(Ref<Sentence> data, Vector2i coord, Symbol tile) {
	for (Vector2i at{ 0, 0 }; at.y < this->factor; ++at.y) {
		for (; at.x < this->factor; ++at.x) {
			data->set_at(coord * this->factor + at, tile);
		}
		at.x = 0;
	}
}

bool ResizeRule::try_apply(Ref<Sentence> sentence) {
	Vector2i size_before{ sentence->size };
	Vector<Symbol> before{ sentence->symbols };
	sentence->set_size(size_before * this->factor);
	for (Vector2i at{ 0, 0 }; at.y < size_before.y; ++at.y) {
		for (; at.x < size_before.x; ++at.x) {
			fill_area(sentence, at, before.get(at.x + at.y * size_before.x));
		}
		at.x = 0;
	}
	sentence->difficulty_map_scale *= this->factor;
	return true;
}

bool TagDepthRule::try_apply(Ref<Sentence> sentence) {
	sentence->read_flip_h = sentence->read_flip_v = sentence->read_transposed = false;
	int start_idx = sentence->symbols.find(Terminals::Start);
	Vector<Vector2i> open{ { start_idx % sentence->size.x, start_idx / sentence->size.x } };
	HashMap<Vector2i, Vector2i> previous{};
	sentence->difficulty_map_scale = 1;
	while (!open.is_empty()) {
		Vector2i current{ open[0] };
		open.remove_at(0);
		int current_difficulty{ -1 };
		switch (sentence->get_at(current)) {
			case Terminals::Start:
				current_difficulty = 0;
				break;
			case Terminals::PointOfInterest:
				current_difficulty = sentence->difficulty_map[previous[current]] + 1;
				break;
			default:
				current_difficulty = sentence->difficulty_map[previous[current]];
				break;
		}
		if (!sentence->difficulty_map.has(current)) {
			sentence->difficulty_map[current] = current_difficulty;
			for (Vector2i neighbour{ -1, -1 }; neighbour.y <= 1; ++neighbour.y) {
				for (; neighbour.x <= 1; ++neighbour.x) {
					Vector2i coord{ current + neighbour };
					if (coord != current && coord.x >= 0 && coord.x < sentence->size.x && coord.y >= 0 && coord.y < sentence->size.y && sentence->get_at(coord) != U'u') {
						open.push_back(coord);
						previous[coord] = current;
					}
				}
				neighbour.x = -1;
			}
		}
	}
	print_line("Difficulty map:");
	for (Vector2i pos{ 0, 0 }; pos.y < sentence->size.y; ++pos.y) {
		String line{};
		for (; pos.x < sentence->size.x; ++pos.x) {
			int difficulty{ sentence->difficulty_at(pos) };
			line += difficulty < 0 ? " " : vformat("%d", difficulty);
		}
		print_line(line);
		pos.x = 0;
	}
	return true;
}

bool PlaceEndRule::try_apply(Ref<Sentence> sentence) {
	Vector2i best_candidate{ -1, -1 };
	int best_difficulty{ -1 };
	for (KeyValue<Vector2i, int> kvp : sentence->difficulty_map) {
		if (sentence->get_at(kvp.key) == Terminals::PointOfInterest && kvp.value > best_difficulty) {
			best_candidate = kvp.key;
			best_difficulty = kvp.value;
		}
	}
	if (best_difficulty > 0) {
		sentence->set_at(best_candidate, Terminals::Goal);
		return true;
	}
	return false;
}