【JavaScript＆HTML5講座】トップページへ

2-5 ソートとサーチ

ゲーム制作や一般的なプログラミングで必要となる知識にソートとサーチがあります。 ソートは複数の数値を決まった順番に並べ替えること、サーチは数値などのデータから目的の値を見つけ出すことをいいます。 本項ではソートとサーチをゲームでの具体例を交え解説します。
今回のソースコードはHTMLのinput要素とtextarea要素を用いて書かれています。それらの要素の説明は(3)で行います。

(1)ソートのアルゴリズム

画面に複数のキャラクターを表示する時、キャラクターの立ち位置によって表示の前後関係が生じます。 次のような斜め上から見下ろす画面構成で考えてみましょう。 このようなゲームでは図①のように画面の上の方に位置するキャラや物体が先に描かれ、下の方に位置するものは後で描かれます。 正しい順番に表示しないと②の丸で囲った部分のようなことが起こります。

①正しい表示順②間違った表示順
　　　　

正しい前後関係で表示するには、キャラクターの座標の値を元に表示順番を決めてから描く必要があります。 この図のようなゲームではY座標の値が小さなキャラから順に描きます。 その順番を決める処理をソートで行います。

ソートを行うサンプルプログラム（ランダムな数値を小さなものから順に並べ替えるアルゴリズム）を見てみましょう。
［ｎ個の配列］ボタンを押すとランダム値が入った要素数ｎの配列が用意され、 ［バブルソート］を押すとそれらの値を小さなものから順に並べ替えます。
example251.html　←　動作の確認
ソースコードは次のようになります。
01<!DOCTYPE html>
02<html lang="ja">
03<head>
04<meta charset="utf-8">
05<title>JavaScriptのテストプログラム</title>
06</head>
07<body>
08<input type="button" value="３個の配列" onclick="makeAry(3)">
09<input type="button" value="５個の配列" onclick="makeAry(5)">
10<input type="button" value="７個の配列" onclick="makeAry(7)">
11<input type="button" value="１０個の配列" onclick="makeAry(10)">
12<hr>
13<div id="mytable"></div>
14<hr>
15<input type="button" value="バブルソート" onclick="sort()">
16<hr>
17<textarea rows="24" cols="70" id="tarea"></textarea>
18
19<script>
20var ary = [];
21var N = 0;
22
23function makeAry( max ) {
24 N = max;
25 var i;
26 for( i = 0; i < N; i ++ ) ary[i] = parseInt( Math.random()*100 );
27
28 //テーブルを表示する
29 var TBL = "<table><tr>";
30 for( i = 0; i < N; i ++ ) TBL = TBL + "<td> [" + i + "] </td>";
31 TBL += "</tr><tr>";
32 for( i = 0; i < N; i ++ ) TBL = TBL + "<td style='background-color:#ccc;'>" + ary[i] + "</td>";
33 TBL += "</tr></table>";
34 eID("mytable").innerHTML = TBL;
35}
36
37function sort() {
38 var i, j, k, t;
39 var n = 0;
40 var SPRO = "";
41
42 for( i = 0; i < N-1; i ++ ) {
43  for( j = 0; j < N-1-i; j ++ ) {
44   if( ary[j] > ary[j+1] ) {
45    t = ary[j]; ary[j] = ary[j+1]; ary[j+1] = t;
46   }
47
48//↓ここから　ソートする過程を表示するための処理
49   n ++;
50   SPRO = SPRO + "(" + n + ") i=" + i + " j=" + j + " : ";
51   for( k = 0; k < N; k ++ ) SPRO = SPRO + ary[k] + " / ";
52   SPRO += "\n";//改行
53//↑ここまで　ソートのアルゴリズムとは無関係
54  }
55 }
56 eID("tarea").value = SPRO + n + "回の比較で並べ替え完了";
57}
58
59function eID( id ) { return document.getElementById( id ); }
60
61</script>
62</body>
63</html>

数値を並べ替えるアルゴリズムは色々ありますが、 その中でバブルソートは判りやすい方法の１つです。 バブルソートは次の図のように、配列[n]の値を隣の[n+1]の値と比べ、[n]の方が大きければ[n]と[n+1]を入れ替えることを繰り返し、数値を並べ替えていきます。 要素数Nの配列で、N-1回比較（必要な場合は入れ替え）すれば、一番大きな数が一番右（[N-1]）に移ります。

次は[0]と[1]、[1]と[2]、[2]と[3]、計N-2回の比較と入れ替えを行えば、二番目に大きな数が[N-2]に入ります。 （ポイント：一番大きな数は既に一番右にあるので、その手前まで比較と入れ替えを行えばよい）
同様に次は[0]と[1]及び[1]と[2]、最後は[0]と[1]の比較と入れ替えで、小さなものから順に数値が並びます。

[n]と[n+1]の比較で[n]の方が小さい時に入れ替えれば、大きな数から順に並ばせることができます。 このアルゴリズムは、大きな数（もしくは小さな数）が泡のように浮かび上がるイメージからバブルソートと呼ばれるそうです。 今回のソースコードは、バブルソートを行う関数内にソートの過程を表示する処理が入っていますので、念のためバブルソートの処理だけを以下に記します。

for( i = 0; i < N-1; i ++ ) {
 for( j = 0; j < N-1-i; j ++ ) {
  if( ary[j] > ary[j+1] ) {
   t = ary[j]; ary[j] = ary[j+1]; ary[j+1] = t;
  }
 }
}


バブルソートのforループとifについて
インターネットでバブルソートを調べると、多くのサイトで、
for( i = 0; i < N-1; i ++ ) {
 for( j = N-1; j > i; j -- ) {
  if( a[j] < a[j-1] ) ‥‥‥
と j のループを減算( j-- )にして、左隣の値（a[j-1]）と比較していく例が載っています。
私がC言語のアルゴリズムを学んだ良書（インターネット普及前に書かれた古い本）には、 まさにこれと同じソースコードが載っていますので、書籍の知識がネット上で普及したと考えています。
さて本講座の解説では、iもjも加算で右隣の値（a[j+1]）と比較するようにしました。 これは本講座の目標である“プログラム初心者の方にできるだけ判りやすく”という観点から、 二重ループを加算と減算ではなく加算だけにして、上図のように左から右に向かって行くほうが感覚的に判りやすいと考えたからです。 どちらの方法でもアルゴリズムは何ら変わりませんので（検索回数も一緒です）、念のためその旨記しておきます。


(2)サーチのアルゴリズム

何かの条件を満たす値を探し出すアルゴリズムもよく使われます。 ゲームでは例えば
・ロールプレイングゲームで体力の一番低下したパーティメンバーを敵が狙ってくる（体力値によるサーチ）
・アクションゲームで攻撃対象を一番近くにいるキャラとする（距離によるサーチ）
などです。
サーチの最も簡単なアルゴリズムは、数値を順に調べて対象となる値を見つけ出す逐次探索です。 乱数で発生させた値をキャラクターの体力に見立て、それが一番低いキャラの番号を探すサンプルを用意しました。
example252.html　←　動作の確認
ソースコードは次のようになります。
01<!DOCTYPE html>
02<html lang="ja">
03<head>
04<meta charset="utf-8">
05<title>JavaScriptのテストプログラム</title>
06</head>
07<body>
08<input type="button" value="１０人分のキャラクター配列" onclick="makeAry(10)">
09<hr>
10<div id="mytable"></div>
11<hr>
12<input type="button" value="体力が一番低いキャラを探す" onclick="search()">
13<hr>
14<input type="text" id="tbox" size="50">
15
16<script>
17var ary = [];
18var N = 0;
19
20function makeAry( max ) {
21 N = max;
22 var i;
23 for( i = 0; i < N; i ++ ) ary[i] = parseInt( Math.random()*100 );
24
25 //テーブルを表示する
26 var TBL = "<table><tr><td>番号</td>";
27 for( i = 0; i < N; i ++ ) TBL = TBL + "<td> [" + i + "] </td>";
28 TBL += "</tr><tr><td>体力</td>";
29 for( i = 0; i < N; i ++ ) TBL = TBL + "<td style='background-color:#cfc;'>" + ary[i] + "</td>";
30 TBL += "</tr></table>";
31 eID("mytable").innerHTML = TBL;
32}
33
34function search() {
35 var i;
36 var min = 100;
37 var chr = -1;
38 for( i = 0; i < N; i ++ ) {
39  if( ary[i] < min ) {
40   min = ary[i];
41   chr = i;
42  }
43 }
44 eID("tbox").value = "体力が一番低いキャラは [" + chr + "] です";
45}
46
47function eID( id ) { return document.getElementById( id ); }
48
49</script>
50</body>
51</html>

値を順に調べていくだけで特に難しいことは行っていませんが、 より小さな値が見つかったらそれを記憶して（ min = ary[i]; ）検索を続けるところがポイントです。 今回は体力の最大値を100と仮定して、比較する初期値を100としていますが( var min = 100; )、この初期値は各プログラムで変更する必要があります。
最も低い体力のキャラが２体以上いる場合（ary[2]=0,ary[9]=0などの時）、結果は小さな方の[n]となります（この場合は[2]）

◇コラム◇　ソートとサーチには色々なアルゴリズムがあります
ここで解説したソートとサーチは、それぞれ最もスタンダードな方法で、複雑なソースコードを書かなくて実現できるアルゴリズムです。 一般的なゲームソフトで同時に登場するキャラは数体から十数体、どんなに多くても数十体ですから、解説した方法で難なく対応できます。 一方、数万、数十万という莫大なデータを並べ替えたり、調べるソフトでは処理の高速化という考えが必要になることがあります。 ここで解説したソートとサーチは効率的なアルゴリズムかというと、そうではありません。 バブルソートは配列の要素数が増えると比較回数はどんどん多くなり、数字が順に並んでいた場合でも無条件に（つまり無駄に）比較を繰り返すことになります。 逐次探索も無条件に全ての数を調べています。
ソートとサーチには効率を追求したアルゴリズムがありますので、興味をもたれた方はネットや書籍でお調べ頂ければと思います。


(3)HTMLのコントロール（ＵＩ）を使う

ユーザーからの入力を扱うためのHTML要素をフォーム(form)といいます。 例えば企業のホームページにはユーザーがメールを送信できるフォームが設置されていることがあります。 アンケートを受け付けているホームページもあります。 そのようなユーザーがＷｅｂサーバーに情報を送る仕組みに使うものがフォームで、 inputやtextareaを次のようにフォームに配置します。
【例】

<form action="*****" method="post">
 <input type="*****">
  :
 <textarea id="*****"></textarea>
</form>


inputやtextareaは今回のソースコードのようにJavaScriptを用いてプログラムの確認に使ったり、ゲーム画面を構成するＵＩとして利用できます。 その場合はフォームに配置する必要はありません。

inputはユーザーからの入力を受け付ける様々なコントロール（ＵＩ）を配置する要素です。 コントロールの種類をtype属性で指定します。今回は汎用ボタンとテキストボックスとして使っています。
・汎用ボタン

<input type="button" value="ボタンに表示する文字" onclick="ボタンが押された時の処理">

・テキストボックス（１行の入力部）

<input type="text" size="何文字入力できるか" value="初期の文字列">


textareaは複数行の入力部を配置する要素です。

<textarea rows="行数" cols="幅（文字数）">（初期の文字列を表示したい場合ここに記述）</textarea>


inputは開始タグのみで記述し、textareaは開始タグ～終了タグで記述します。
テキストボックスとテキストエリアは本来はテキスト入力に使いますが、今回はソートやサーチの結果表示に使っています。 テキストエリアは、そこに表示した文字列をコピーペーストして使いたい場合、divやp要素を書き換えて文字列を表示するよりコピペしやすいので便利です。

ＵＩ、ＧＵＩ、コントロール
パソコンやスマートフォンの画面でユーザー入力を受け付ける部分を ＵＩ（ユーザーインターフェイス）やＧＵＩ（グラフィカルユーザーインターフェイス）といいます。 HTMLではinputやtextareaをコントロールと呼びます。 ここで解説したものはそれらのほんの一部です。 他にもinputのtype属性でチェックボックスを配置したり、select要素で選択式のメニューを表示できます。 またHTML5では便利なコントロールが追加されました。 例えば色を選択する<input type="color">や、日付を入力する<input type="date">です。 それらをJavaScriptと組み合わせれば高度な処理を行うソフトウェアが制作できますし、ゲームの開発ツールなども作ることができます。 フォームやコントロールに関する詳しい解説は本講座の目指すところではございませんので割愛しますが、 興味を持たれた方はぜひネットでお調べ頂ければと思います。


前のページへ　／　次のページへ
お気軽にお問い合わせ下さい →