.NET - *Теория*(VB.NET || C#.net ) Нужен алгоритм для мини - игры

[ssdm]

Добрый день!

Игра: есть поле 8 х 8 ячеек(изначально серого цвета), игрок имеет право ходить только буквой "Г" и только в ещё не пройденный квадрат(пройденный квадрат меняет цвет на красный).

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

Нужен алгоритм позволяющий заполнять поле после n>=0 ходов игрока.. Может кто нить знает где его можно взять или есть идеи как построить алгоритм?...

Заранее благодарю.

[CyberDaemon]

Цитата:



компьютер заполнял оставшееся поле с учетом выше перечисленных правил



Т.е. компьютер должен сам сходить "буквой Г"?

Ну и чего сложного? Массив 8х8, "непохоженное" поле - 0, похоженное - "1". Из текущего положения капм пытается сходить буквой Г, если там единичка - то пытается сходить по-другому, если больше вариантов хода для него нет - то все...

[CyberDaemon]

Цитата:



будет жутко медленным, и оптимитизация его затруднена



Значит задачу надо пытаться свести к решению более мелких задач, типа заполнения полей 4х4 так, чтобы можно было из них "собрать" 8х8

[DedAlex]

Задачи такого типа решаются с помощью рекурсии, и единственный вариант - полный перебор всех вариантов. Насколько я знаю математического решения нет.

[ssdm]

Цитата:



Т.е. компьютер должен сам сходить "буквой Г"?

Ну и чего сложного? Массив 8х8, "непохоженное" поле - 0, похоженное - "1". Из текущего положения капм пытается сходить буквой Г, если там единичка - то пытается сходить по-другому, если больше вариантов хода для него нет - то все...



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

думаю существует какое то математическое решение..

[ssdm]

CyberDaemon

DedAlex

ок.. прийду домой попробую написать.. но возникает такой вопрос:

Изначально я создаю массив кнопок 8 на 8( поле).. попутно создал массив 8 на 8 типа boolean(true - пройденная ячейка, false - непройденное ячейка).. так вот, как быстрее будет работать программа: если работать с массивом булеан или лучше создать целочисленный массив или вообще использовать свойство уже существующего массива кнопок .tab(mas(i,j) - массив кнопок, mas(i,j).tag=1 - пройденная кнопка-ячейка, mas(i,j).tag=0 - непройденная) ?

[CyberDaemon]

ssdm


Цитата:



от 1 до 8 вариантов ходов(допустим игрок сделал один ход, это ж сколько переборов сделать надо



Полагаю, от одного до восьми на каждый ход. При условии, что они с игроком по очереди ходят.



Или игрок должен начать, а компьютер после этого "ходом коня пройти все поле, не попадая дважды в одну и ту-же клетку"? Тогда простор для фантазии в самом деле огромный, и перебором _это_ решать...

[ssdm]

Цитата:



Или игрок должен начать, а компьютер после этого "ходом коня пройти все поле, не попадая дважды в одну и ту-же клетку"? Тогда простор для фантазии в самом деле огромный, и перебором _это_ решать...



именно так )

[bezumes]

Цитата:



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

думаю существует какое то математическое решение..



при маленьком количестве закрашеных клеток комп решение будет быстро находить(потому что куда ни плюнь везде пусто





А при занятых количестве клеток больше допустим 3/4. Можно сделать так:

Взять оставшиеся пустые клетки и проверять можно ли туды ходить.А если заняты все клетки то gane over and happy end.

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









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

[ssdm]

bezumes

это не шахматы..

играю я один.. а комп это что то вроде подсказки..


Цитата:



при маленьком количестве закрашеных клеток комп решение будет быстро находить(потому что куда ни плюнь везде пусто



мало просто сходить, надо сходиь так, что бы закрасить все поле..