DouKaku?beta

challenge ラングトンのアリの描画

ラングトンのアリを描画してください。ラングトンのアリは、以下のような動きをする、セル・オートマトンです。(Wikipediaより引用)
- 黒いマスにアリがいた場合、90°右に方向転換し、そのマスの色を反転させ、1マス前進する。
- 白いマスにアリがいた場合、90°左に方向転換し、そのマスの色を反転させ、1マス前進する。
詳しくはWikipedia等で調べるか、参考ページに拙作のデモがありますのでご覧下さい。

see: JavaScriptでラングトンの蟻 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html lang="ja">
<head>
       <meta http-equiv="content-type" content="text/html;charset=utf-8">
       <meta http-equiv="content-script-type" content="text/javascript">
       <meta http-equiv="content-style-type" content="text/css">
       <title>ラングトンの蟻</title>
<style type="text/css">
#canvas{
       border: 1px solid #999;
       width: 300px;
       height: 300px;
}
#canvas div{
       width: 3px;
       height: 3px;
       float: left;
}
</style>
<script>
var earth = [];
var WORLD_SIZE = 100;
var lang_ant;

function Ant(){}
Ant.prototype = {
    age : 0,
    ageDisplay : undefined,
    id : undefined,
    speed: 200,
    direction: [0,-1],//向き。x軸 y軸。最初は上に動く
    position: [60,40],//初期位置
    world: [],
    start: function(){
        var self = this;
        this.id = setInterval(function(){self.move()}, 1000/this.speed);
    },
    move: function(){
        this.ageDisplay.innerHTML = ++this.age;
        this.moveNextCell();
        var cell = this.getCellInfo();
        var color = cell.getAndToggleColor();
        this.setNextDirection(color);
    },
    moveNextCell: function(){
        this.position[0] += this.direction[0];
        this.position[1] += this.direction[1];
        if(this.position[0] < 0 || this.position[1] < 0 ||
           this.position[0] >= WORLD_SIZE || this.position[1] >= WORLD_SIZE){
            clearInterval(this.id);
            this.die();
        }
    },
    getCellInfo: function(){
        var idx = this.position[0] + this.position[1] * WORLD_SIZE;
        return this.world[idx];
    },
    setNextDirection: function(bool){//colorがfalse(白)なら右へ、true(黒)なら左へ転回
        if(bool){//黒
            var tmp = this.direction[0];
            this.direction[0] = this.direction[1];
            this.direction[1] = -tmp;
        }
        else{//白
            var tmp = this.direction[0];
            this.direction[0] = -this.direction[1];
            this.direction[1] = tmp;
        }
    },
    die: function(){
        alert('Langton\'s ant is dead.');
        throw true;
    }
};

function Cell(elm){
    this.elm = elm;
}
Cell.prototype = {
    elm: undefined,
    color: false, //colorは2値なのでbooleanで表す
    colorList: ['#FFF','#000'],
    getAndToggleColor: function(){
        this.color = !this.color;
        var i = this.color ? 1 : 0;
        this.elm.style.backgroundColor = this.colorList[i];
        return !this.color;
    }
}
window.onload = function(){
    var canvas = document.getElementById('canvas');
    var div = '<div></div>';
    var inner_canvas = "";
    for(var i=0; i< WORLD_SIZE*WORLD_SIZE; i++){
        inner_canvas += div;
    }
    canvas.innerHTML = inner_canvas;
    
    var cells = canvas.childNodes;
    for(var i=0; i<cells.length; i++){//世界の誕生
        earth[i] = new Cell(cells[i]);
    }
    lang_ant = new Ant();//蟻の誕生
    lang_ant.world = earth;//地球に降り立つ
    lang_ant.ageDisplay = document.getElementById('step');
    
    document.getElementById('run').disabled = false;
}
</script>
</head>
<body>
<p><input type="button" value="run" onclick="lang_ant.start();this.disabled=true;" id="run" disabled="disabled">　<span id="step"></span>
　<input type="button" value="stop &amp; refresh" onclick="location.reload();"></p>
<div id="canvas"></div>
post comment

Posted feedbacks - JavaScript

ラングトンのアリを描画してください。ラングトンのアリは、以下のような動きをする、セル・オートマトンです。(Wikipediaより引用)
- 黒いマスにアリがいた場合、90°右に方向転換し、そのマスの色を反転させ、1マス前進する。
- 白いマスにアリがいた場合、90°左に方向転換し、そのマスの色を反転させ、1マス前進する。
詳しくはWikipedia等で調べるか、参考ページに拙作のデモがありますのでご覧下さい。

see: JavaScriptでラングトンの蟻 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html lang="ja">
<head>
       <meta http-equiv="content-type" content="text/html;charset=utf-8">
       <meta http-equiv="content-script-type" content="text/javascript">
       <meta http-equiv="content-style-type" content="text/css">
       <title>ラングトンの蟻</title>
<style type="text/css">
#canvas{
       border: 1px solid #999;
       width: 300px;
       height: 300px;
}
#canvas div{
       width: 3px;
       height: 3px;
       float: left;
}
</style>
<script>
var earth = [];
var WORLD_SIZE = 100;
var lang_ant;

function Ant(){}
Ant.prototype = {
    age : 0,
    ageDisplay : undefined,
    id : undefined,
    speed: 200,
    direction: [0,-1],//向き。x軸 y軸。最初は上に動く
    position: [60,40],//初期位置
    world: [],
    start: function(){
        var self = this;
        this.id = setInterval(function(){self.move()}, 1000/this.speed);
    },
    move: function(){
        this.ageDisplay.innerHTML = ++this.age;
        this.moveNextCell();
        var cell = this.getCellInfo();
        var color = cell.getAndToggleColor();
        this.setNextDirection(color);
    },
    moveNextCell: function(){
        this.position[0] += this.direction[0];
        this.position[1] += this.direction[1];
        if(this.position[0] < 0 || this.position[1] < 0 ||
           this.position[0] >= WORLD_SIZE || this.position[1] >= WORLD_SIZE){
            clearInterval(this.id);
            this.die();
        }
    },
    getCellInfo: function(){
        var idx = this.position[0] + this.position[1] * WORLD_SIZE;
        return this.world[idx];
    },
    setNextDirection: function(bool){//colorがfalse(白)なら右へ、true(黒)なら左へ転回
        if(bool){//黒
            var tmp = this.direction[0];
            this.direction[0] = this.direction[1];
            this.direction[1] = -tmp;
        }
        else{//白
            var tmp = this.direction[0];
            this.direction[0] = -this.direction[1];
            this.direction[1] = tmp;
        }
    },
    die: function(){
        alert('Langton\'s ant is dead.');
        throw true;
    }
};

function Cell(elm){
    this.elm = elm;
}
Cell.prototype = {
    elm: undefined,
    color: false, //colorは2値なのでbooleanで表す
    colorList: ['#FFF','#000'],
    getAndToggleColor: function(){
        this.color = !this.color;
        var i = this.color ? 1 : 0;
        this.elm.style.backgroundColor = this.colorList[i];
        return !this.color;
    }
}
window.onload = function(){
    var canvas = document.getElementById('canvas');
    var div = '<div></div>';
    var inner_canvas = "";
    for(var i=0; i< WORLD_SIZE*WORLD_SIZE; i++){
        inner_canvas += div;
    }
    canvas.innerHTML = inner_canvas;
    
    var cells = canvas.childNodes;
    for(var i=0; i<cells.length; i++){//世界の誕生
        earth[i] = new Cell(cells[i]);
    }
    lang_ant = new Ant();//蟻の誕生
    lang_ant.world = earth;//地球に降り立つ
    lang_ant.ageDisplay = document.getElementById('step');
    
    document.getElementById('run').disabled = false;
}
</script>
</head>
<body>
<p><input type="button" value="run" onclick="lang_ant.start();this.disabled=true;" id="run" disabled="disabled">　<span id="step"></span>
　<input type="button" value="stop &amp; refresh" onclick="location.reload();"></p>
<div id="canvas"></div>


自分のマシンは CPUが Pentium 4 (2.66GHz)、メモリが 512MBとリ
ソースが貧弱なためか、うまく動作してくれませんでした。

なので、 #9331を参考に table要素を利用したものへと書き直して
みました。

念のため、以下のブラウザーで動作を確認してあります。

  Firefox 2.0.0.6
  Internet Explorer 6.0.29
  Google Chrome 1.0.154.48
  Opera 9.23
  Safari 3.1.2

Firefox, Google Chrome, Safariは CPUをほとんど食わないのです
が、 Internet Explorerと Operaはともに CPU使用率が高く、動作
も遅かったです。(実装の違いですかね? )
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
<html>
<head>
    <style type="text/css">
        .C_0 { background-color : #ffffff; height : 3px; width : 3px; }
        .C_1 { background-color : #000000; height : 3px; width : 3px; }
    </style>
    <script type="text/javascript">
        Function.prototype.repeat = 
        function (t, o) {
            var _ = this;
            return setInterval(function () { _.apply(o); }, t);
        };

        var $ = function (i) { return document.getElementById(i); };

        var USER_AGENT = navigator.userAgent.toLowerCase();
        var CLASS_NAME = (USER_AGENT.indexOf('msie') > -1) ? 'className' : 'class';

        var Colony = 
        function (w, h) {
            this.w = w;
            this.h = h;
            this.generate = 
            function () {
                var i, j;

                document.write('<table border="0" cellpadding="0" cellspacing="0">');
                for (j = 0; j < this.h; j++) {
                    document.write('<tr>');
                    for (i = 0; i < this.w; i++) document.write('<td id="' + i + '_' + j + '" class="C_0"></td>');
                    document.write('</tr>');
                }
                document.write('</table>');
            };
        };

        var Ant = 
        function (x, y, w, h) {
            this.x  = x;
            this.y  = y;
            this.dx = -1;
            this.dy = 0;
            this.w  = w;
            this.h  = h;
            this.id = 0;
            this.move = 
            function () {
                var C = $(this.x + '_' + this.y);
                var c;
                var t;

                if (this.x < 0 || this.x >= this.w || this.y < 0 || this.y >= this.h) {
                    alert('DEAD END ...');
                    clearTimeout(this.id);
                    return;
                }

                if (c = ((C.getAttribute(CLASS_NAME)).split('_')[1] ^ 1)) { // 反転
                    t = this.dx;
                    this.dx = this.dy;
                    this.dy = -t;
                } else {
                    t = this.dx;
                    this.dx = -this.dy;
                    this.dy = t;
                }

                C.setAttribute(CLASS_NAME, 'C_' + c);

                this.x += this.dx;
                this.y += this.dy;

                if (!this.id) this.id = this.move.repeat(10, this);
            };
        };
    </script>
</head>
<body>
    <script type="text/javascript">
        var W = 100, H = 100;
        new Colony(W, H).generate();
        new Ant(50, 50, W, H).move();
    </script>
</body>
</html>

アリの動作をどう書くかという話じゃなく、余談にはなりますが、参考ページのブログエントリに書かれていたビットマップ表現と効率について。

DOMのあるノード直下に非常に多数のノードを作る（兄弟ノードが多すぎる）・それらのノードにアクセスするというのは、速度低下の原因になりがちです。どのくらいの数からどこに影響が出るかは実装によるでしょうが、ノード総数が少々多くなろうとも入れ子・小分けにすることで改善できる場合があります。

添付コードのように変更を加えた場合、Pen4 2.53GHzにおいて時間を計測すると次のようになりました（単位:ms ― 遅いCPUだから差が顕著になっているのであって、今時のCPUではこれほどの改善は見込めないかもしれませんが）。

Firefox 3.5.1:
キャンバス作成（ノード作成）が34,551から1,021へと大幅に改善、アリの行進（ノードアクセス）でも330,770から216,934に改善
Opera 10b1:
キャンバス作成は328から344にと若干遅くなるが、もともとあまり時間が掛かっていない。アリの行進の方は1,188,625から415,312に改善

一方で、テーブル要素にしてしまう方法も試してみましたが、手元の環境ではdiv要素で小分けとほとんど変わりませんでした。セルの色表現を、要素のクラス書き換え・クラスごとにCSSで色指定する方法も試してみたが、こちらでもほとんど変化なし。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
<style type="text/css">
#canvas{
       border: 1px solid #999;
       width: 300px;
       height: 300px;
}
/* 子divへのCSS指定を、孫divへの指定にするだけ */
#canvas div div{
       width: 3px;
       height: 3px;
       float: left;
}
</style>



// スクリプト部の変更点はwindow.onloadのコールバックのみ

window.onload = function(){
// キャンバス作成部 セルを表すdivを入れ子に
    var canvas = document.getElementById('canvas');
    var k = 0;
    for(var i=0; i< WORLD_SIZE; i++){
        var row = document.createElement('div');
        canvas.appendChild(row);
        for(var j=0; j< WORLD_SIZE; j++){
            var cell = document.createElement('div');
            row.appendChild(cell);
            earth[k] = new Cell(cell);
            k++;
        }
    }
// 以下変更なし
    lang_ant = new Ant();//蟻の誕生
    lang_ant.world = earth;//地球に降り立つ
    lang_ant.ageDisplay = document.getElementById('step');
    
    document.getElementById('run').disabled = false;
}

出題者によるデモが初期読み込み時に重かったので、改編してみました。

おまけにアリ自体も最大5匹まで増量可能だったり。

ちなみにOperaだとCSSのエラーで動かないっぽいのが難点ですorz

see: サンプル 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
<html>
  <head>
    <meta http-equiv="content-type" content="text/html;charset=shift_jis">
    <title>Langton's Ant</title>
    <script type="text/javascript"><!-- //
langton={};

langton.Direction=function(x,y){ this.x=(x)?x:0; this.y=(y)?y:0; };

langton.Direction.prototype={
  x : 0,
  y : 0,
  equals : function(test){
             return (this.x==test.x)&&(this.y==test.y);
           },
  change : function(dif){
             var val=langton.Direction.next(this,dif);
             this.x=val.x;
             this.y=val.y;
             return this;
           }
 };

langton.Direction.NORTH=new langton.Direction(0,-1);
langton.Direction.SOUTH=new langton.Direction(0,1);
langton.Direction.EAST=new langton.Direction(1,0);
langton.Direction.WEST=new langton.Direction(-1,0);

langton.Direction.CYCLE=[
  langton.Direction.NORTH,
  langton.Direction.EAST ,
  langton.Direction.SOUTH,
  langton.Direction.WEST
];

langton.Direction.FORWORD=0;
langton.Direction.RIGHT=1;
langton.Direction.BACKWORD=2;
langton.Direction.LEFT=3;

langton.Direction.next=function(current,change){
  var i = 0;
  for( ; i < langton.Direction.CYCLE.length; i++){
    if(current.equals(langton.Direction.CYCLE[i])){ break; }
  }
  i+=change;
  i%=langton.Direction.CYCLE.length;
  return langton.Direction.CYCLE[i];
};

langton.Ant=function(){};

langton.Ant.prototype={
  x : -1,
  y : -1,
  direction : null,
  color : null,
  go : function(lr){
         this.direction=this.direction.change(lr);
         this.x+=this.direction.x;
         this.y+=this.direction.y;
         if(this.x==langton.Canvas.rowsize){ this.x=0; }
         if(this.x<0){ this.x=langton.Canvas.rowsize-1; }
         if(this.y==langton.Canvas.rowsize){ this.y=0; }
         if(this.y<0){ this.y=langton.Canvas.rowsize-1; }
         return this;
       },
  eat : function(cell,isblack){
          var color = (isblack)?this.color:langton.Canvas.BLACK;
          cell.style.backgroundColor=color;
        },
  action : function(cells){
             var index = this.y*langton.Canvas.rowsize + this.x;
             if(!cells[index]){
               cells[index]=langton.Canvas.prepareCell();
               cells[index].style.position="absolute";
               cells[index].style.top=(this.x*3)+"px";
               cells[index].style.left=(this.y*3)+"px";
             }
             var isblack=(cells[index].style.backgroundColor==langton.Canvas.BLACK);
             this.eat(cells[index],isblack);
             var choice = (isblack) ? langton.Direction.RIGHT
                                    : langton.Direction.LEFT;
             this.go(choice);
             return this;
           }
};

langton.Canvas={};

langton.Canvas.body=null;
langton.Canvas.counter=null;

langton.Canvas.rowsize=100;
langton.Canvas.cells=[];

langton.Canvas.clear=function(){
  if(langton.Canvas.counter){
    langton.Canvas.counter.value=0;
    langton.Canvas.counter=null;
  }
  if(langton.Canvas.body){
    langton.Canvas.body.innerHTML="";
    langton.Canvas.body=null;
  }
  langton.Canvas.ants=[];
  langton.Canvas.cells=[];
};

langton.Canvas.ants=[];

langton.Canvas.BLACK="black";
langton.Canvas.WHITE="white";
langton.Canvas.BLUE="blue";
langton.Canvas.RED="red";
langton.Canvas.YELLOW="yellow";
langton.Canvas.GREEN="green";

langton.Canvas.COLORS=[
  langton.Canvas.WHITE,
  langton.Canvas.BLUE,
  langton.Canvas.RED,
  langton.Canvas.YELLOW,
  langton.Canvas.GREEN
];

langton.Canvas.prepareCell=function(){
  var div = document.createElement("div");
  langton.Canvas.body.appendChild(div);
  div.style.width="3px";
  div.style.height="3px";
  div.style.backgroundColor=langton.Canvas.BLACK;
  return div;
};

langton.Canvas.addAnt=function(){
  if(langton.Canvas.ants.length < langton.Canvas.COLORS.length){
    var ant =new langton.Ant();
    ant.x=Math.floor(Math.random()*langton.Canvas.rowsize);
    ant.y=Math.floor(Math.random()*langton.Canvas.rowsize);
    ant.color=langton.Canvas.COLORS[langton.Canvas.ants.length];
    var dirid = Math.floor(Math.random()*langton.Direction.CYCLE.length);
    var dir = langton.Direction.CYCLE[dirid];
    ant.direction=new langton.Direction(dir.x,dir.y);
    langton.Canvas.ants.push(ant);
  };
};

langton.Action=function(){
  if(!langton.Canvas.body){
    langton.Canvas.body=document.getElementById("canvas");
  }
  if(langton.Canvas.ants.length==0){
    langton.Canvas.addAnt();
  }
  for(var i = 0; i < langton.Canvas.ants.length; i++){
    langton.Canvas.ants[i].action(langton.Canvas.cells);
  }
  if(!langton.Canvas.counter){
    langton.Canvas.counter=document.getElementById("counter");
  }
  var value = parseInt(langton.Canvas.counter.value,10)+1;
  langton.Canvas.counter.value=value;
};

/* -------------------------------------------------------------------------------- */
langton.timer=0;
langton.isTimerOn=false;

langton.startTimer=function(){
  langton.isTimerOn=true;
  document.getElementById("run").disabled=true;
  document.getElementById("clear").disabled=true;
  langton.timer = setInterval(langton.executeTimer, 1);
};

langton.stopTimer=function(){
  langton.isTimerOn=false;
};

langton.executeTimer=function(){
  if(langton.isTimerOn) langton.Action();
  else{
    clearInterval(langton.timer);
    document.getElementById("run").disabled=false;
    document.getElementById("clear").disabled=false;
    return 0;
  }
};

function test(){
  langton.Action();
}

    // --></script>
    <style type="text/css">
#canvas{
       border: 1px solid #999;
       width: 300px;
       height: 300px;
       background-color: black;
}
    </style>
  </head>
  <body>
    <p>
      <input type="button"
             value="run"
             onclick="langton.startTimer();"
             id="run" />
      <input type="button"
             value="add"
             onclick="langton.Canvas.addAnt();" />
      <input type="button"
             value="stop"
             onclick="langton.stopTimer();" />
      <input type="button"
             value="clear"
             onclick="langton.Canvas.clear()"
             id="clear" />
      <input type="text" id="counter" disabled value=0 />
    </p>
    <div id="canvas" style="position:relative"></div>
  </body>
</html>

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]