Какой алгоритм наиболее эффективен для проверки правильности размещения слов на игровом поле и запуска игры «Окончено», ⇐ C#

[Anonymous]

Каковы подробности вашей проблемы?
Я разрабатываю игру, похожую на «Эрудит», и мне нужно реализовать алгоритм, который запускает состояние Игра окончена. когда ни один игрок не может разместить правильное слово, используя имеющиеся у него плитки на открытых слотах доски. В игре участвуют несколько игроков, у каждого из которых есть плитки, которые они могут разместить на доске.
Конкретная проблема заключается в том, чтобы определить, могут ли доступные игроку плитки составить допустимое слово в любой из открытых (пустых) плиток. позиции на доске. Если ни одно правильное слово не может быть составлено, игра заканчивается и определяется победитель.
Мои опасения:

• Слова-префиксы: слова, которые можно расширить, добавив плитки в начало существующих слов на доске.
• Слова-суффиксы: слова, которые можно расширить, добавив плитки в конце существующих слов.
• Слова-инфиксы: слова, которые можно образовать, помещая плитки в середине свободного пространства между существующими буквами.
• Эффективность. Алгоритм должен выполняться во время хода каждого игрока, а перебор всех возможных плиток и комбинаций слов может занять слишком много времени. Ему необходимо быстро проверять все возможные слова, не вызывая задержек во время игры.

Проблема, с которой я столкнулся:

• Алгоритм, который я сейчас использую, либо неправильно определяет все возможные варианты размещения слов, либо его выполнение занимает слишком много времени, особенно во время хода каждого игрока.
• Возможно, я слишком усложняю проблему или упускаю более эффективное решение.

В чем мне нужна помощь:

• Советы или альтернативные подходы для эффективного определения допустимого размещения слов (с учетом регистров префиксов, суффиксов и инфиксов).
• Предложения по оптимизации алгоритма для обеспечения высокой производительности в ходе пошагового игрового цикла.

Что вы пробовали и чего ожидали?
Я реализовал рекурсивный логический метод, чтобы проверить, доступны ли какие-либо допустимые ходы на игровом поле, похожем на «Эрудит». Функция просматривает плитки каждого игрока и пытается найти возможные места размещения слов на доске, проверяя действительные плитки и открывая соседние плитки. Идея состоит в том, что во время хода игрока алгоритм должен определить, можно ли составить правильное слово, используя доступные плитки.
Мои ожидания:
Я ожидал, что алгоритм правильно определить, когда может быть сформировано допустимое слово, и вернуть true.
Если допустимые слова не могут быть созданы, метод должен вернуть false, сигнализируя о том, что игру, возможно, необходимо завершить или у игрока не осталось действительных ходов.
Что на самом деле происходит:
Я продолжаю получать ложные результаты, указывающие на отсутствие действительных ходов, даже когда должны быть доступны действительные ходы. В сообщениях Debug.Log постоянно указывается «Нет допустимого слова», и игра продолжается так, как будто никакие слова не могут быть сформированы, что неверно.
Я подозреваю, что либо мне не хватает некоторых допустимых мест размещения слов, либо рекурсивный метод природа алгоритма не рассматривает все возможности, как ожидалось.
Вот код, который я использовал:
Метод сначала проверяет плитки каждого игрока, просматривает все допустимые плитки на доске и пытается разместить плитки на соседние позиции для формирования действительных слов:
void OnSubmit()
{
if (AnyValidMovesAvailable(board))
{
Debug.Log("Valid Moves Available");
}
else
{
Debug.Log("No Valid Moves Available");
}
}
public bool AnyValidMovesAvailable(Board board)
{
// Create Unplaced Potential Letters using the remaining Unplaced Tiles
foreach (var playerInfo in PlayerInfoManager.Instance.GetAllPlayerInfos())
{
List unPlacedPotentialLetters = playerInfo.GetPlayerTiles()
.Select(tile => new PotentialLetter(tile, false))
.ToList();

List potentialWord = new List();

// Loop through all the valid tiles on the board to check possible word placements
foreach (var validTiles in wordValidator.GetValidTiles())
{
foreach (var validTile in validTiles.GetValidTiles())
{
BoardTile boardTile = validTile.tileProperties.boardTile;

// Check if a valid word can be placed starting from this tile
if (moveAvailabilityChecker.PossibleValidMoves(board, boardTile, potentialWord, unPlacedPotentialLetters, wordValidator))
{
Debug.Log("There is a Valid Word");
return true;
}
else
{
Debug.Log("No Valid Word Found");
}
}
}
}

// If no valid word was found, return false
return false;
}

public bool PossibleValidMoves(Board board, BoardTile validBoardTile, List potentialValidWord, List unPlacedPotentialLetters, WordValidator wordValidator)
{
WordEvaluation wordEvaluation = new WordEvaluation();
Tile validTile = validBoardTile.GetTile();

// Add the Valid Tile as a Potential Letter (first tile)
if (potentialValidWord.Count == 0)
{
PotentialLetter potentialLetter = new PotentialLetter(validTile, true);
potentialValidWord.Add(potentialLetter);
}

// Perform an Order using the Position on the board (sorts potential word)
OrderPotentialWord(potentialValidWord);

// Get neighboring board tiles (prefix, infix, suffix positions)
List neighborBoardTiles = board.GetNeighboringBoardTiles(validBoardTile);

// Loop over all possible neighboring tiles
foreach (var neighborBoardTile in neighborBoardTiles)
{
// Skip if the neighboring tile already has an unplaced tile
if (!neighborBoardTile.HasUnPlacedTile())
{
foreach (var unPlacedPotentialLetter in unPlacedPotentialLetters)
{
// Ensure valid letter placement (skip invalid placements if needed)
if (!IsValidPlacement(potentialValidWord.Last(), unPlacedPotentialLetter))
{
continue; // Skip invalid placements
}

// Place the letter temporarily in the neighbor tile
neighborBoardTile.SetUnPlacedTile(unPlacedPotentialLetter.tile);
unPlacedPotentialLetter.possiblePosition = neighborBoardTile.GetBoardPosition();

// Create new potential word and update remaining unplaced letters
List newPotentialWord = new List(potentialValidWord) { unPlacedPotentialLetter };
List newRemainingUnplacedLetters = new List(unPlacedPotentialLetters);
newRemainingUnplacedLetters.Remove(unPlacedPotentialLetter);

// Check if the current word could already be valid before recursion
if (IsValidWordSoFar(newPotentialWord, wordEvaluation))
{
// If valid, return true and stop further exploration
Debug.Log($"Valid word found: {string.Join("", newPotentialWord.Select(e => e.value))}");
return true;
}

// Recursively search from this new neighbor (DFS)
if (PossibleValidMoves(board, neighborBoardTile, newPotentialWord, newRemainingUnplacedLetters, wordValidator))
{
return true;
}

// Backtrack: reset the neighbor and remove the last letter added
neighborBoardTile.SetUnPlacedTile(null);
newPotentialWord.RemoveAt(newPotentialWord.Count - 1);
}
}
}

// Construct the word string after exploring all neighbors
string possibleWordString = string.Join("", potentialValidWord.Select(e => e.value));

// Base case: if the word is valid, return true
if (wordValidator.IsValidWord(possibleWordString))
{
Debug.Log($"Valid word found: {possibleWordString}");
return true;
}

// No valid word found
return false;
}



Подробнее здесь: https://stackoverflow.com/questions/790 ... s-on-a-gam