2

任何人都可以建议一种合适的方法来计算网格上允许的棋子移动,类似于下图中的网格。

网格布局

假设piece1在a1位置,piece2在c3位置,如果piece1可以移动(比如说)3个方格,而piece2可以移动2个方格,我怎么知道哪些方格是允许移动的?

我似乎花了太长时间开发基于文本的 MUDS,即使在最简单的情况下,我也根本无法让我的大脑采取下一步措施来可视化潜在的运动。

如果这很重要,我会尝试在 javascript 中执行此操作,但老实说,我认为我在这里的失败是未能正确概念化 - 而不是语言理解方面的失败。

更新 - 我正在添加在发布以下回复后编写的第一轮代码。我认为查看代码可能对与我处于类似情况的人有用

它很草率,到目前为止它仅适用于放置在板上的一个项目,但至少该check_allowable_moves()功能适用​​于此初始运行。对于那些想知道为什么我要创建那些奇怪的字母数字对象而不仅仅是使用数字 x 轴和 y 轴的人 - 这是因为 HTML 中的 id 不能以数字开头。事实上,假装我可以使用数字来开始 id 对理解我得到的奇妙答案所描述的功能和概念有很大帮助。

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="application/xhtml+xml;utf-8"/>

<title>Test page</title>
<style> 

    #chessboard { clear: both; border:solid 1px black; height: 656px; 
                  width:656px; /*width = 8*40 + 16 for border*/ }
    #chessboard .row { overflow: auto; clear: both; }
    #chessboard .row span { display: block; height: 80px; 
                            width: 80px; float: left; 
                            border:solid 1px black; }
    .allowable { background: blue; }
</style>
<script type="text/javascript" src="http://www.google.com/jsapi"></script>
<script type="text/javascript">
    google.load("jquery", "1.2.6");
    google.load("jqueryui", "1.5.3");
</script>
<script type="text/javascript">
$(document).ready(function() {
    (function() {
    var global = this;
    global.Map = function(container) {
        function render_board() {
        var max_rows = 8;
        var cols = new Array('a','b', 'c', 'd', 'e', 'f', 'g', 'h');
        var jqMap = $('<div />');
        jqMap.attr('id', 'chessboard');
        var x=0;
        for(x; x<max_rows; x++) {
            var jqRow = $('<span />');
            jqRow.addClass('row');
            var i=0;
            for(i; i<cols.length; i++) {
                var jqCol = $('<span />');
                jqCol.attr('id', cols[i]+(x+1));
                jqCol.addClass(cols[i]);
                jqRow.append(jqCol);
            }
          jqMap.append(jqRow);
        }
     $('#'+container).append(jqMap);
   }
   function add_piece(where, id) {
     var jqPiece = $('<div>MY PIECE'+id+'</div>');
     var jqWhere = $('#'+where);
     jqPiece.attr('id', 'piece-'+id);
     jqPiece.addClass('army');
     jqPiece.draggable({cursor: 'move',
                              grid:[82, 82],
                              containment: '#chessboard',
                              revert: 'invalid',
                              stop: function(ev, ui) {
                                //console.log(ev.target.id);
                              }
                            });
     jqWhere.append(jqPiece);
     check_allowable_moves(where);
    }
    function check_allowable_moves(location) {
     var x_axis = { 'a':1,'b':2, 'c':3, 'd':4, 'e':5, 'f':6, 'g':7, 'h':8 };
     var x_axis_alpha = { 1:'a',2:'b', 3:'c', 4:'d', 5:'e', 6:'f', 7:'g', 8:'h' };
     $('.allowable').droppable("destroy");
     $('.allowable').removeClass('allowable');
     //get the x,y values of the piece just placed
     var x = parseInt(x_axis[location[0]], 10);
     var y = parseInt(location[1], 10);
     var x_min = x-2;
     var y_min = y-2;
      for(x_min; x_min<=x+2; x_min++) {
        for(y_min; y_min<=y+2; y_min++) {
           var jqCell = $('#'+x_axis_alpha[x_min]+y_min)
           jqCell.addClass('allowable');
           jqCell.droppable({ accept: '.army',
              drop: function(ev, ui) {
                //console.log(ev, ui, $(this));
                //handle_drop(ev, ui, $(this));
                check_allowable_moves($(this).attr('id'));
              }
            });
        }
        y_min = parseFloat(y)-2;
      }
    }
    render_board();
    add_piece('d5', '2');
   }
 })();
var map = new Map('content');
});
</script>
</head>

<body id="debug">
    <div id="page">
        <div id="content"> </div>
    </div><!-- end page -->
</body>
</html>
4

4 回答 4

3

假设 p 位于位置 x, y 并且可以将 n 个方格移开到位置 x2, y2。这意味着 (x - x2) 和 (y - y2) 之间的绝对差之和不能大于 n。

如果您要显示可以移动到哪些方格(而不是输入 x2 和 y2),我认为最好在棋子周围的方格中循环所有位置。那是...

for (x - n TO x + n):
    for (y - n TO x + n):
        if (abs(x - x2) + abs(y - y2) <= n):
            mark as okay.

这个答案假设棋子只能移动到相邻的方格而不是对角线。

编辑:如果您想要对角线移动,并且沿对角线移动的成本与水平或垂直移动一样多,那么问题实际上要容易得多 - 块 p 可以在 (x - n, x + n) 和(y - n, y + n)。

如果对角线移动的成本不如水平+垂直移动的成本高(例如,如果对角线的成本为 1.5,而 h/v 的成本为 1),那么答案将变得更加复杂。

于 2009-02-03T18:49:25.277 回答
2

一般而言,此类问题涉及人们可能到达的合理有限的网格。取一个网格大小的数据结构,其元素可以以足够的精度保存剩余运动点的数量。

将网格初始化为未访问的值。这不得在零到最大可能移动速度的范围内。负值是理想的。

将起始位置初始化为剩余的移动次数。

此时有三种可能的方法:

1)每一步重新扫描整个网格。简单但速度较慢。终止是当没有点产生合法的举动时。

2)将点存储在堆栈上。比#1 快,但仍然不是最好的。终止是堆栈为空时。

3) 将点存储在队列中。这是最好的。终止是队列为空时。

Repeat
   ObtainPoint {From queue, stack or brute force}
   For Each Neighbor do
      Remaining = Current - MovementCost
      If Remaining > CurrentValue[Neighbor] then
         CurrentValue[Neighbor] = Remaining
         Push or Queue Neighbor
Until Done

请注意,使用基于堆栈的方法时,您总是会遇到一些最终丢弃旧计算并再次执行它们的情况。只有在某些情况下绕过恶劣地形比通过它便宜时,基于队列的方法才会发生这种情况。

仅在循环结束时检查终止条件,否则在获取点尝试使用空队列或堆栈时终止。获得点之后的空队列/堆栈并不意味着你已经完成了!

(请注意,这是对伊恩答案的相当大的扩展。)

于 2009-02-03T19:43:34.513 回答
1

这纯粹是在概念层面上,但试试这个逻辑:

  1. 将所有可能的位置从您的起点移走一步并将它们放在堆栈上(已采取的移动 =0)

  2. 从堆栈中弹出一个并重复,使用该新坐标作为您的新起点。(采取的行动=1)。您必须确保不要在堆栈上放置任何重复的坐标

  3. 重复 2 直到你用尽了所有可用的动作。

我可能无法很好地解释这一点,如果您对我要说的内容有任何疑问,请告诉我。

于 2009-02-03T18:53:52.100 回答
0

您可以使用上述方法,但改用递归。

递归“深度”是移动距离。

当深度 > 运动时爆发。

每次迭代都应该返回一个空间向量并添加它自己的位置。

删除重复项

于 2009-02-03T19:20:46.493 回答