Алгоритм дерева

Question

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

1) Я мог бы реализовать круговой n-связанный список. Но так как список ходов никогда не заканчивается, я боюсь, что это может вызвать переполнение стека ™. Идея состоит в том, что каждый узел будет иметь n дочерних элементов, и после получения команды он может привести вас к одному из его дочерних элементов или, если ни одна дочерняя группа не будет доступна для такой команды, привести вас к началу. По прибытии на любого ребенка, пара функций будет выполнена, вызывая маленький и большой эффект. Это может, однако, привести к множеству дублированных узлов в дереве, чтобы справиться со всеми возможными последовательностями, заканчивающимися на этом конкретном движении с различными эффектами, что может быть затруднительно, но я не уверен. Я никогда не пробовал что-то такое сложное в коде, только теоретически. Этот алгоритм существует и имеет имя? Это хорошая идея?

2) Я мог бы реализовать конечный автомат. Тогда вместо того, чтобы бродить по связанному списку, у меня был бы гигантский вложенный переключатель, который вызывал бы функции и соответственно обновлял состояние машины. Кажется, проще в реализации, но ... ну ... не кажется забавным ... и не элегантным. Гигантские переключатели всегда кажутся мне безобразными, но будет ли это работать лучше?

3) Предложения? Я хороший, но я далеко неопытный. Хорошая вещь поля кодирования в том, что как бы странно ни была ваша проблема, кто-то решил ее в прошлом, но вы должны знать, где искать. У кого-то может быть идея получше, чем у меня, и я действительно хотел услышать предложения.

Answer 1

Я не совсем уверен, что я точно понимаю, о чем вы говорите, но в качестве анагональной ситуации, скажем, кто-то вводит бесконечный поток цифр на клавиатуре. «117» - это волшебная последовательность, «468» - это еще одна, «411799» - это другая (которая содержит первую).

Итак, если пользователь вводит:

55468411799

вы хотите запустить «магические события» на * s:

55468 *4117* 99 *

или что-то в этом роде, верно? Если это аналогично проблеме, о которой вы говорите, то что-то вроде (Java-подобный псевдокод):

MagicSequence fireworks = new MagicSequence(new FireworksAction(), 1, 1, 7);
MagicSequence playMusic = new MagicSequence(new MusicAction(), 4, 6, 8);
MagicSequence fixUserADrink = new MagicSequence(new ManhattanAction(), 4, 1, 1, 7, 9, 9);

Collection<MagicSequence> sequences = ... all of the above ...;

while (true) {
  int num = readNumberFromUser();
  for (MagicSequence seq : sequences) {
    seq.handleNumber(num);
  }
}

в то время как MagicSequence имеет что-то вроде:

Action action = ... populated from constructor ...;
int[] sequence = ... populated from constructor ...;
int position = 0;

public void handleNumber(int num) {
  if (num == sequence[position]) {
    // They've entered the next number in the sequence
    position++;
    if (position == sequence.length) {
       // They've got it all!
       action.fire();
       position = 0; // Or disable this Sequence from accepting more numbers if it's a once-off
    }
  } else {
    position = 0; // missed a number, start again!
  }
}

Answer 2

В любом случае вы можете захотеть реализовать конечный автомат, но вам не нужно жестко кодировать переходы состояний.
Попробуйте составить график состояний, где связь между состоянием A и состоянием B будет означать, что A может привести к B.
Затем вы можете просмотреть график во время выполнения, чтобы найти, куда игрок идет.

Редактировать: Вы можете определить узел графа как:
-состояние-ID
-список ссылок на другие государства, где каждая ссылка определяет:
-состояние-идентификатор
-условие, список состояний, которые необходимо посетить перед переходом в это состояние

Answer 3

@ Коуэн, @ Хавьер: Хорошая идея, не против, если я добавлю к ней?

Пусть объекты MagicSequence прослушивают входящий поток ввода пользователя, то есть уведомляют их о входе (широковещании), и позволяют каждому из них добавлять вход в свой внутренний поток ввода. Этот поток очищается, когда вход не является ожидаемым следующим входом в шаблоне, в котором MagicSequence запускает свое действие. Как только шаблон завершен, запустите действие и очистите внутренний входной поток.

Оптимизируйте это, подавая только входные данные в ожидающие его магические последовательности. Это можно сделать двумя способами:

1. У вас есть объект, который позволяет всем MagicSequence соединяться с событиями, которые соответствуют номерам в их шаблонах. MagicSequence (1,1,7) добавит себя в got1 и got7, например:

   UserInput.got1 + = MagicSequnece [i] .SendMeInput;

2. Вы можете оптимизировать это так, чтобы после каждого ввода MagicSequence отменялось регистрацию недействительных событий и регистрировалось с действительными.

Answer 4

создать небольшой конечный автомат для каждого эффекта, который вы хотите. при каждом действии пользователя «транслируйте» его на все конечные автоматы. большая часть этого не будет заботиться, но некоторые продвинутся, или возможно пойдут назад. когда один из них достигнет своей цели, произведите желаемый эффект.

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

edit: Кажется, что совет Коуэна эквивалентен этому, но он оптимизирует свои конечные автоматы, чтобы выразить только простые последовательности. кажется достаточно для вашей конкретной проблемы, но более сложные условия могут потребовать более общего решения.

Answer 5

То, что вы описываете, звучит несколько похоже на граф зависимостей или граф слов. Вы можете посмотреть на них.

Answer 6

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

Answer 7

То, что вы описываете, звучит очень похоже на дерево технологий в игре Live Civilization.

Я не знаю, как авторы Civ построили свои, но я был бы склонен использовать мультиграф для представления возможных «ходов» - будут некоторые, с которых вы можете начать без «опыта», и когда в них будет несколько путей до конца.

Нарисуйте, какие потенциальные варианты вы можете иметь на каждом этапе игры, а затем начертите линии, переходящие от одних вариантов к другим.

Это должно дать вам начало реализации, поскольку графики - это [относительно] простые концепции для реализации и использования.