اطلاعات جمع آوری شده در خصوص الگوریتم A-Star

من هنوز درس هوش مصنوعی نخوندم و حقیقتا این اولین مطالعه ام در مورد هوش مصنوعی بود ، پس مجددا از سر نخ ممنون ، نتیجه گیری من این بود : یک الگوریتم مسیر یابی | تعیین هدف هست ، مزیتی که داره ( نمیدونم سایر الگوریتم ها دارن یا نه :| چون نیاز به مطالعه کامل سایر الگوریتم ها داره :| ) اینه که میزان تلاش برای رسیدن به هدف از مسیر های مختلف در هر قدم قابل برآورد هست ، یعنی ما در قدم اول میگیم این مسیر x پیمایش نیاز داره ، اون مسیر y پیمایش ، پس مسیر کوتاه تر مسیر x هست ، در اولین نگاه به یک تصویر متوجه شدم که عملکرد بسیار نزدیک به هوش انسان داره ، چرا که همیشه مسیری انتخاب میشه ، که ما رو به هدف نزدیک تر میکنه ( که در واقع بهترین قدم در اون شرایط هست ) با مطالعه ی بیشتر متوجه شدم بهش میگن "اولین بهترین" - این نتیجه ی نیم ساعتی تحقیق بود، ولی فکر کنم بتونم خرگوش َ رو برسون خونشون ، جوری که آقا گرگه نخورتش :)

در مبحث مسیر یابی یه مقاله برا سال 2010 دیدم . چکیدش رو اینجا میزارم:

Pathfinding is one of the tasks, apart from graphics rendering, requiring most CPU resources. Although

there are many approaches to effectively solve pathfinding problems, they are becoming less suitable

as more and more games have larger game worlds that dynamically change during the game play. These

new games have more visually realistic graphics that increase the game characters realism but all these

efforts may be useless if game characters perform dumb movements or follow inappropriate paths such

as repeatedly walking close to an enemy or a predator while moving from one location to another. To

tackle this problem we present in this paper an ant colony algorithm for path finding that takes into

account the emotions of the game characters and we show how our approach is used in an aug-mented-reality educational game. The proposed algorithm is implemented on a GPU processor to dem-onstrate its scalability with large problem sizes when compared to its corresponding CPU version.

من الگوریتم کولونی مورچه ها رو بلدم. البته توی نرم افزار متلب.به نظرم استفاده از الگوریتم های تکاملی و هوش جمعی در بازی سازی میتونه جالب باشه. فقط ایرادی که همیشه به الگوریتم های تکاملی وارده اینه که سرعتشون خیلی زیاد نیست. حالا اینکه سرعت کم این الگوریتم ها چقدر ما رو در ساختن بازی محدود میکنن رو باید از اساتید بازی سازی پرسید.توی بحث یافتن مسیر در پازل مطرح شده ، میشه یه گراف طراحی کرد که برای هر خانه  جدول یه گره در نظر گرفت و وزن هر یال رو فاصله منهتن تا نقطه هدف در نظر گرفت. البته این فاصله با توجه به موانع موجود،بصورت تخمینی محاسبه میشه و برای یافتن نزدیک ترین مسیر میتونه کمک کنه. این شبیه کاریه که توی این سایت دیدم:http://mp.tabin.ir/57/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D9%85%D8%B3%DB%8C%D8%B1%DB%8C%D8%A7%D8%A8%DB%8C-a-%DA%86%DB%8C%D8%B3%D8%AA/ 

سلام خدمت استاد عزیز و دوستان گلم :)

جوابی که A.L.U دادن کاملا درسته ولی من چون قبلا توی دانشگاه یه چیزایی درباره این الگوریتم خوندم رو اینجا مینویسم تا سر نخ خوبی بشه واسه ادامه تحقیقاتتون :)

خوب، قبل از این که بگم *A چی هست باید یک گام بیایم عقب تر و یه چند تا از اصطلاحات و مفاهیمی که به درک بهتر از *A کمکمون میکنه یاد بگیریم.

قبل از هر چیز باید بدونیم که *A یک جستجوی آگاهانه هست، حالا این جستجوی آگاهانه چیه؟ 

به عنوان مثال(از مثال استاد که توی نظری که بالا دادن استفاده میکنم.): 

شما فرض کنید خودتون توی میدون جنگ هستید و هی به سمت دشمن تیر اندازی میکنید، حالا بعد از این که همه تیر هاتون تموم شد هر چقدر هم که شلیک کنید تفنگ هی تق تق میکنه و هیچ تیری شلیک نمیکنه و شما میدونید که خشاب خالیه ولی وقت ندارید که خشاب رو عوض کنید پس میاید یه FlashBang میندازید جلوی دشمن تا یه فرصت بدست بیارید که مثلا اسلحه رو عوض کنید و مثلا با کلت کمری به سمت دشمن شلیک کنید. حالا دلیل این که این مثال رو زدم چی بود؟ 

شما وقتی توی موقعیتی مثل مثال بالا قرار بگیرید طبق تجربتون و اطلاعاتی که واسه رهایی از این مخمصه دارید استفاده میکنید و راه حل رو پیدا میکنید. پس یعنی شما میدونید که یه کلت کمری دارید، یه flashBang دارید، و خشاب پر شده و آماده دارید و میاید بررسی میکنید که الان با این ابزار هایی که در اختیار دارید بهتره که چه کاری رو انجام بدید. (دلیل این که یخورده با جزئیات زیاد توضیح دادم این بود که از این مثال استفاده کنیم و بتونیم برای ماشین(کامپیوتر) راحتتر پیاده سازیش کنیم.)؛ به این میگن جستجوی آگاهانه یا اکتشافی (heuristic)، پس وقتی یه الگوریتم بخواد دنبال یه جواب بگرده و از قبل هم اطلاعاتی درباره رسیدن به جواب داشته باشه و بر اساس این اطلاعات به دنبال جواب بگرده میگیم از جستجوی آگاهانه استفاده کرده.

جستجوی آگاهانه خودش شامل چند تا روش هست که ما الان با یکی از اونا به اسم جستجوی اول - بهترین(best - first search یا greedy search) کار داریم که *A معروف ترین فرم جستجوی اول بهترین هست.

خوب، اول ببینیم که جستجوی اول - بهترین (حریصانه) چیه ؟

این الگوریتم مثل یه آدم حریص عمل میکنه، مثال بالا رو در نظر بگیرید - من (یه آدم حریص :) ( البته فقط تو یادگیری حریصم :) ) ) خودمو میذارم به جای اون کسی که وسط جنگ خشابش خالی میشه و میخوام بهترین کاری رو که به ذهنم میرسه تو اون لحظه انجام بدم، خوب اگه بخوام تو کشتن دشمن حرص بزنم میام به جای این که خشاب عوض کنم، سریع کلت کمری خودمو در میارم و به سمت دشمن تیر اندازی میکنم، این به نظر راه خوبی میاد، درسته؟  آره درسته :) چون با کلت همه دشمنا رو کشتم.

ولی این الگوریتم یه عیب داره، که با همین مثال ادامه میدم :

این کاری که من کردم ( شلیک با کلت کمری ) درسته که یکی از کارهایی هست که منطقی به نظر میاد ولی ممکنه جوابی که ما میخوایم نباشه، میگید چرا؟ میگید که دشمنا رو کشتیم؟ نهههه اشتباه میکنید کلتی که من داشتم خیلی ضعیف بود و به راحتی دشمن رو از پا در نمیاره. (مشکل دقیقا همین جا پیش میاد ):

1. اطلاعات من کافی نیست، چون من نمیدونستم که این کلت نمیتونه دشمن رو از پا در بیاره و راه حل بهتر این بود که من اول flashBang بندازم بعد توی زمانی که بدست آوردم خشاب رو عوض کنم و ... 

2. شایدم من میدونستم که این کلت نمیتونه دشمن رو از پا در بیاره ولی سریع ترین راهی که به ذهنم میرسید این بود.

نتیجه میگیریم که الگوریتم حریصانه همیشه بهترین جواب رو پیدا نمیکنه ولی سعی داره که هر چقدر میتونه به جواب نزدیکتر بشه.

اگه بخوایم یکم تخصصی تر بحث کنیم میتونیم اینطور بگیم :

اگر (f(n رو یک تابع ارزیابی برای رسیدن به جواب در نظر بگیریم و (h(n رو هزینه تخمینی کم هزینه ترین راه حل از حالت فعلی به حالت هدف در نظر بگیریم؛ و چون این الگوریتم از فقط از تابع (h(n برای رسیدن به جواب کمک میگیره پس میتونیم چنین چیزی رو براش بنویسم: (f(n) = h(n

*نکته : (h(n ی قابل قبول هست که هزینه رسیدن به هدف رو بیشتر از هزینه واقعی تخمین نزنه.

از این فرمول هم این طور میتونیم برداشت کنیم که این الگوریتم فقط به دنبال کم هزینه ترین راه حل میگرده و به همین خاطر ممکنه جواب مطلوبی به ما نده.

پس با این مثال ما دیدیم که الگوریتم اول - بهترین / حریصانه چطور کار میکنه و عیبش چیه.

حالا بریم ببینیم معروفترین فرم جستجوی اول - بهترین ( *A ) چیه ؟

از اون جایی که *A یک الگوریتم حریصانه هست پس برای رسیدن به جواب از (h(n کمک میگیره و البته از یه تابع دیگه به اسم (g(n هم کمک میگیره. 

 (g(n چیه ؟ 

واسه این که (g(n رو بتونم بهتر توضیح بدم یه مثال دیگه میزنم، چون با مثال بالا نتونستم یه مثال واضح برای  (g(n بزنم و از اونجایی که واسه درک بهتر این جور الگوریتم ها بیشتر از مثال های مسیر یابی استفاده میکنن منم یه همچین مثالی میزنم.عکس زیر رو ببینید:

*توجه : اعداد استفاده شده در شکل حقیقی نمیباشند و به صورت تصادفی انتخاب شده اند.

الان (g(n توی این شکل میشه همون عددایی که روی خطوط قرمز نوشتم یعنی فاصله هر شهر با شهر دیگه، و (h(n هم میشه 650 (کوتاهترین راهی که از مبدا به مقصد هست همون خط صافی هست که بینشون میکشیم که اینجا 650 هست).

حالا با هم میبینیم که الگوریتم *A چطور مسیر مناسب رو از سیستان به سمت کردستان پیدا میکنه.

من فقط دو مرحله از این مسیر رو رسم کردم که شکل خیلی بزرگ نشه و فکر میکنم تا همین جا هم واسه توضیح دادن *A کفایت میکنه.

اول از همه ما میایم همه راه هایی که از سیستان به سمت کردستان رو داریم حساب رسم میکنیم. که در مرحله اول از سیستان میتونیم به خراسان، کرمان و هرمزگان بریم. بعد از این که هر 3 تا node رو گسترش دادیم، میایم تابع ارزیابیشونو طبق فرمولی که قبلا گفتم حساب میکنیم. مثلا برای خراسان میشه:

f(n) = فاصله خط مستقیم سیستان به کردستان + فاصله سیستان به خراسان 

وقتی که تابع ارزیابی همه node ها رو حساب کردیم، باید اون node ی رو گسترش بدیم که کمترین مقدار رو داره که توی مثال ما خراسان واجد شرایط هست.

حالا همه node هایی که از خراسان به کردستان میرسند رو گسترش میدیم ( من توی شکل فقط یک راه رو رسم کردم که درختی که رسم میشه خیلی بزرگ نشه). و تابع ارزیابی همشون رو حساب میکنیم. 

بعد از این که تابع ارزیابی همه زیر شاخه های خراسان رو حساب کردیم، باید بین همه node های باقیمانده (اونایی که هنوز گسترش ندادیم | توی شکل با رنگ سبز نشون داده شده.) اون node ی که کمترین مقدار رو داره پیدا کنیم و گسترش بدیم.

این طرز عملکرد *A بود البته با استفاده از الگوریتم tree-search که به نظر من تا همین جا واسه آشنایی کافیه و الگوریتم graph-search رو به خودتون میسپارم.

الان دیگه دستم خسته شد، بقیش باشه واسه بعد :).

خب استاد ایده رو مطرح کردن، دوستان توضیح دادن، منم نوشتمش :)

هم کدهاش رو میذارم هم لینکشو . این لینک برنامه اندرویدش (با جاوا نوشتم که همه بچه های اینجا بتونن runش کنن)

خروجی رو به محض اجرای برنامه توی log مشاهده کنید (tag:answer)( اون دکمه الکیه فقط برا قشنگیه D:)

شماره اول شماره سطر و شماره دوم شماره ستون رو برمیگردونه

توضیحاتشو دادم. من نقشه همین سوال استاد(بالای صفحه) رو روش پیاده کردم ولی شما میتونید هر مپی که میخواید رو روش پیاده کنید. فقط باید dimension و اون مقادیر آرایه ها رو تغییر بدید

خیلی استاندارد ننوشتم. به بزرگواری خودتون ببخشید ;)

 package test.sadeghbarout.a_star;

import java.util.ArrayList;
import android.app.Activity;
import android.os.Bundle;
import android.util.Log;


/*
 * ------------------- Written by sadeghbarout
 * --------------------- sbarotcob@gmail.com
 */

public class A_StarActivity extends Activity {

    private static final int dimension = 12;                          // اندازه ضلع مربع  نقشه + 2
    int[][]                  map;                                     // نقشه بازی
    private StructCalcs      start     = new StructCalcs();           // خانه شروع
    private StructCalcs      end       = new StructCalcs();           // خانه پایان
    private StructCalcs      now       = new StructCalcs();           //خانه فعلی
    private boolean          endofGame;                               //بررسی پایان بازی
    ArrayList<StructCalcs>   whiteList = new ArrayList<StructCalcs>(); //لیست سفید برای خانه های قابل تردد
    ArrayList<StructCalcs>   blackList = new ArrayList<StructCalcs>(); // لسیت سیاه برای خانه هایی که قبلا تردد شده
    ArrayList<StructCalcs>   finalPath = new ArrayList<StructCalcs>(); // مسیر صحیح نهایی

    int                      g         = 0;                           // محاسبه حرکتهای انجام شده


    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.main);

        //ساخت و مقدار دهی آرایه نقشه زمین
        map = new int[dimension + 2][dimension + 2];
        for (int i = 1; i < dimension + 1; i++) {
            for (int j = 1; j < dimension + 1; j++) {
                map[i][j] = 0;
            }
        }

        // مشخص کردن شکل نقشه
        /*
         * 0 خانه آزاد
         * 1 دیوار
         * 2 start
         * 3 end 
         */
        // دقت کتید که مختصه اول شماره سطر و مختصه دوم شماره ستون ه
        map[10][1] = 2;
        map[1][10] = 3;

        map[1][4] = 1;
        map[1][6] = 1;
        map[2][2] = 1;
        map[2][6] = 1;
        map[2][8] = 1;
        map[3][2] = 1;
        map[3][3] = 1;
        map[3][4] = 1;
        map[3][6] = 1;
        map[3][8] = 1;
        map[4][4] = 1;
        map[4][8] = 1;
        map[5][1] = 1;
        map[5][2] = 1;
        map[5][4] = 1;
        map[5][5] = 1;
        map[5][6] = 1;
        map[5][7] = 1;
        map[5][8] = 1;
        map[5][9] = 1;
        map[6][1] = 1;
        map[6][6] = 1;
        map[7][3] = 1;
        map[7][4] = 1;
        map[7][6] = 1;
        map[7][8] = 1;
        map[7][9] = 1;
        map[7][10] = 1;
        map[8][6] = 1;
        map[9][2] = 1;
        map[9][4] = 1;
        map[9][5] = 1;
        map[9][6] = 1;
        map[9][7] = 1;
        map[9][8] = 1;
        map[9][9] = 1;
        map[10][2] = 1;

        //یافتن خانه شروع و پایان
        for (int i = 1; i < dimension + 1; i++) {
            for (int j = 1; j < dimension + 1; j++) {
                int k = map[i][j];
                if (k == 2) {
                    start.x = i;
                    start.y = j;
                } else if (k == 3) {
                    end.x = i;
                    end.y = j;
                }
            }
        }

        //-------------------------------------------------------
        // شروع بررسی
        now = start;
        whiteList.add(now);
        while ( !endofGame) {

            g++;
            calc(up(now), "up");
            calc(left(now), "left");
            calc(down(now), "down");
            calc(right(now), "right");

            blackList.add(now);
            whiteList.remove(indexInList(now, whiteList));
            if (isInList(end, whiteList)) {
                endofGame = true;
                endGame("finded");
            }
            if (whiteList.size() == 0) {
                endofGame = true;
                endGame("noWay");
            } else {
                now = whiteList.get(findMinF(whiteList));
            }
        }
    }


    // پایان بازی  --------------------------------------------
    private void endGame(String status) {

        if (status.equals("finded")) {
            finalPath.add(end);

            // بازگشت مسیر صحیح به عقب
            while ( !(now.x == start.x && now.y == start.y)) {

                if (isInList(up(now), blackList) && now.dir.equals("down")) {
                    finalPath.add(now);
                    now = blackList.get(indexInList(up(now), blackList));
                } else if (isInList(left(now), blackList) && now.dir.equals("right")) {
                    finalPath.add(now);
                    now = blackList.get(indexInList(left(now), blackList));
                } else if (isInList(down(now), blackList) && now.dir.equals("up")) {
                    finalPath.add(now);
                    now = blackList.get(indexInList(down(now), blackList));
                } else if (isInList(right(now), blackList) && now.dir.equals("left")) {
                    finalPath.add(now);
                    now = blackList.get(indexInList(right(now), blackList));
                }
            }
            finalPath.add(now);

            // چاپ مسیر صحیح
            Log.i("answer", "کوتاهترین مسیر در " + finalPath.size() + " حرکت ");
            for (int i = finalPath.size() - 1; i >= 0; i--) {
                Log.i("answer", finalPath.get(i).x + " , " + finalPath.get(i).y);
            }

        }
    }


    // یافتن f حداقل از بین خانه های آرایه ---------------------
    private int findMinF(ArrayList<StructCalcs> ps) {
        int index = 0;
        int min = 500000;
        for (int i = 0; i < ps.size(); i++) {
            if (ps.get(i).f < min) {
                min = ps.get(i).f;
                index = i;
            }
        }
        return index;
    }


    //  انجام محاسبات ----------------------------------
    private void calc(StructCalcs p, String dir) {
        if ( !checkBlock(p)) {
            StructCalcs SC = new StructCalcs();
            SC.x = p.x;
            SC.y = p.y;
            SC.g = g;
            SC.h = distance(p, end);
            SC.f = SC.g + SC.h;
            SC.dir = dir;

            if (isInList(p, whiteList)) {
                if (whiteList.get(indexInList(p, whiteList)).f >= SC.f) {
                    whiteList.remove(indexInList(p, whiteList));
                    whiteList.add(SC);
                }
            } else {
                whiteList.add(SC);
            }
        }
    }


    // یافتن فاصله بین دو خانه --------------
    private int distance(StructCalcs p1, StructCalcs p2) {
        return Math.abs(p1.x - p2.x + p1.y - p2.y);
    }


    // محاسبه خانه بالایی -----------------
    private StructCalcs up(StructCalcs p) {
        StructCalcs pp = new StructCalcs();
        pp.x = p.x;
        pp.y = p.y - 1;
        //p.y--;
        return pp;
    }


    // محاسبه خانه پایینی ----------------
    private StructCalcs down(StructCalcs p) {
        StructCalcs pp = new StructCalcs();
        pp.x = p.x;
        pp.y = p.y + 1;
        // p.y++;
        return pp;
    }


    // محاسبه خانه راستی ----------------
    private StructCalcs right(StructCalcs p) {
        StructCalcs pp = new StructCalcs();
        pp.x = p.x + 1;
        pp.y = p.y;
        //p.x++;
        return pp;
    }


    // محاسبه خانه چپی ----------------
    private StructCalcs left(StructCalcs p) {
        StructCalcs pp = new StructCalcs();
        pp.x = p.x - 1;
        pp.y = p.y;
        //p.x--;
        return pp;
    }


    // بررسی مسدود بودن خانه برای حرکت ------------
    private boolean checkBlock(StructCalcs p) {
        boolean ans = false;
        if (map[p.x][p.y] == 1 || p.x > dimension - 2 || p.y > dimension - 2 || p.x < 1 || p.y < 1)
            ans = true;

        if (isInList(p, blackList)) {
            ans = true;
        }
        return ans;

    }


    // بررسی وجود یک خانه در آرایه ---------------
    private boolean isInList(StructCalcs p, ArrayList<StructCalcs> ps) {
        boolean ans = false;
        for (StructCalcs SC: ps) {
            if (SC.x == p.x && SC.y == p.y) {
                ans = true;
            }
        }
        return ans;

    }


    // یافتن محل یک خانه در آرایه ----------------
    private int indexInList(StructCalcs p, ArrayList<StructCalcs> ps) {
        int ans = 0;
        int index = -1;
        for (StructCalcs SC: ps) {
            index++;
            if (SC.x == p.x && SC.y == p.y) {
                ans = index;
            }
        }
        return ans;

    }
}

اینم کلاس دومش

 package test.sadeghbarout.a_star;

public class StructCalcs {

    public int    x;
    public int    y;
    public int    g;
    public int    h;
    public int    f;
    public String dir;

}