astart.cpp

Astar windows版本 Astar windows版本

#include ".\astart.h"
#include "List.cpp"
#include <math.h>
Astart::Astart(int a[37][64],int w,int l,int s,int e)
{
	for(int i=0; i<l; i++)
	{
		for(int j=0; j<w; j++)
		{
			map[i][j] = a[i][j];
		}
	}
	WIDTH = w;
	start = s;
	end = e;
	LENGTH = l;
	rect = new Rect[WIDTH*LENGTH];
	for(int i=0; i<WIDTH*LENGTH; i++)
	{
		rect[i].map_x = i%WIDTH;
		rect[i].map_y = i/WIDTH;
	}
	rect[start].g_value = 0;
	rect[start].pre = NULL;
}

Astart::~Astart(void)
{
}


bool Astart::Find()
{
	if(close_list.IsEmpty())
	{
		if((start+WIDTH)/WIDTH < LENGTH && (start+WIDTH)/WIDTH >=0 && (start+WIDTH)%WIDTH >= 0 && (start+WIDTH)%WIDTH < WIDTH && start/WIDTH != LENGTH-1)
		{
			if( map[(start+WIDTH)/WIDTH][(start+WIDTH)%WIDTH]!=1 )
			{
				rect[start+WIDTH].pre = &rect[start];
				rect[start+WIDTH].h_value = get_h_value(start+WIDTH);
				rect[start+WIDTH].g_value = get_g_value(start+WIDTH);
				open_list.Insert(open_list.Length(),start+WIDTH);
			}
		}
		if((start-WIDTH)/WIDTH < LENGTH && (start-WIDTH)/WIDTH >=0 && (start-WIDTH)%WIDTH >= 0 && (start-WIDTH)%WIDTH < WIDTH && (start/WIDTH) != 0)
		{
			if( map[(start-WIDTH)/WIDTH][(start-WIDTH)%WIDTH]!=1)
			{
				rect[start-WIDTH].pre = &rect[start];
				rect[start-WIDTH].h_value = get_h_value(start-WIDTH);
				rect[start-WIDTH].g_value = get_g_value(start-WIDTH);
				open_list.Insert(open_list.Length(),start-WIDTH);
			}
		}
		if((start+1)/WIDTH < LENGTH && (start+1)/WIDTH >=0 && (start+1)%WIDTH >= 0 && (start+1)%WIDTH < WIDTH && start!= start/WIDTH * WIDTH + WIDTH-1)
		{
			if( map[(start+1)/WIDTH][(start+1)%WIDTH]!=1)
			{
				rect[start+1].pre = &rect[start];
				rect[start+1].h_value = get_h_value(start+1);
				rect[start+1].g_value = get_g_value(start+1);
				open_list.Insert(open_list.Length(),start+1);
			}
		}
		if((start-1)/WIDTH < LENGTH && (start-1)/WIDTH >=0 && (start-1)%WIDTH >= 0 && (start-1)%WIDTH < WIDTH && start%WIDTH!=0)
		{
			if( map[(start-1)/WIDTH][(start-1)%WIDTH]!=1)
			{
				rect[start-1].pre = &rect[start];
				rect[start-1].h_value = get_h_value(start-1);
				rect[start-1].g_value = get_g_value(start-1);
				open_list.Insert(open_list.Length(),start-1);
			}
		}
		close_list.Insert(close_list.Length(),start);
	}
	int i = 0;
	int num = -1;
	int rectcount = 0;
	for(int z=1; z<=open_list.Length(); z++)
	{
		int counttemp,numtemp;
		open_list.Find(z,counttemp);
		numtemp = rect[counttemp].h_value +  rect[counttemp].g_value;
		if(num==-1)
		{
			num = numtemp;
		}
		if(numtemp <= num)
		{
			i = z;
			num = numtemp;
			rectcount = counttemp;
		}
	}
	int temp;
	if(i==0)
	{
		return false;
	}
	open_list.Delete(i,temp);
	close_list.Insert(close_list.Length(),rectcount);
	if((rectcount+WIDTH)/WIDTH < LENGTH && (rectcount+WIDTH)/WIDTH >=0 && (rectcount+WIDTH)%WIDTH >= 0 && (rectcount+WIDTH)%WIDTH < WIDTH && (rectcount/WIDTH) != LENGTH-1)
	{
		if(rectcount+WIDTH == end)
		{
			rect[rectcount+WIDTH].pre = &rect[rectcount];
			return true;
		}
		if( map[(rectcount+WIDTH)/WIDTH][(rectcount+WIDTH)%WIDTH]!=1 )
		{
			if(close_list.Search(rectcount+WIDTH) == 0)
			{
				if(open_list.Search(rectcount+WIDTH) == 0)
				{
					rect[rectcount+WIDTH].pre = &rect[rectcount];
					rect[rectcount+WIDTH].h_value = get_h_value(rectcount+WIDTH);
					rect[rectcount+WIDTH].g_value = get_g_value(rectcount+WIDTH);
					open_list.Insert(open_list.Length(),rectcount+WIDTH);
				}
				else
				{
					if(rect[rectcount].g_value + 10 < rect[rectcount+WIDTH].g_value)
					{
						rect[rectcount+WIDTH].pre = &rect[rectcount];
						rect[rectcount+WIDTH].g_value = get_g_value(rectcount+WIDTH);
					}
				}
			}
		}
	}
	if((rectcount-WIDTH)/WIDTH < LENGTH && (rectcount-WIDTH)/WIDTH >=0 && (rectcount-WIDTH)%WIDTH >= 0 && (rectcount-WIDTH)%WIDTH < WIDTH && (rectcount/WIDTH) != 0)
	{
		if(rectcount-WIDTH == end)
		{
			rect[rectcount-WIDTH].pre = &rect[rectcount];
			return true;
		}
		if( map[(rectcount-WIDTH)/WIDTH][(rectcount-WIDTH)%WIDTH]!=1)
		{
			if(close_list.Search(rectcount-WIDTH) == 0)
			{
				if(open_list.Search(rectcount-WIDTH) == 0)
				{
					rect[rectcount-WIDTH].pre = &rect[rectcount];
					rect[rectcount-WIDTH].h_value = get_h_value(rectcount-WIDTH);
					rect[rectcount-WIDTH].g_value = get_g_value(rectcount-WIDTH);
					open_list.Insert(open_list.Length(),rectcount-WIDTH);
				}
				else
				{
					if(rect[rectcount].g_value + 10 < rect[rectcount-WIDTH].g_value)
					{
						rect[rectcount-WIDTH].pre = &rect[rectcount];
						rect[rectcount-WIDTH].g_value = get_g_value(rectcount-WIDTH);
					}
				}
			}
		}
	}
	if((rectcount+1)/WIDTH < LENGTH && (rectcount+1)/WIDTH >=0 && (rectcount+1)%WIDTH >= 0 && (rectcount+1)%WIDTH < WIDTH && rectcount!= rectcount/WIDTH * WIDTH + WIDTH-1)
	{
		if(rectcount+1 == end)
		{
			rect[rectcount+1].pre = &rect[rectcount];
			return true;
		}
		if( map[(rectcount+1)/WIDTH][(rectcount+1)%WIDTH]!=1)
		{
			if(close_list.Search(rectcount+1) == 0)
			{
				if(open_list.Search(rectcount+1) == 0)
				{
					rect[rectcount+1].pre = &rect[rectcount];
					rect[rectcount+1].h_value = get_h_value(rectcount+1);
					rect[rectcount+1].g_value = get_g_value(rectcount+1);
					open_list.Insert(open_list.Length(),rectcount+1);
				}
				else
				{
					if(rect[rectcount].g_value + 10 < rect[rectcount+1].g_value)
					{
						rect[rectcount+1].pre = &rect[rectcount];
						rect[rectcount+1].g_value = get_g_value(rectcount+1);
					}
				}
			}
		}
	}
	if((rectcount-1)/WIDTH < LENGTH && (rectcount-1)/WIDTH >=0 && (rectcount-1)%WIDTH >= 0 && (rectcount-1)%WIDTH < WIDTH  && rectcount%WIDTH!=0)
	{
		if(rectcount-1 == end)
		{
			rect[rectcount-1].pre = &rect[rectcount];
			return true;
		}
		if( map[(rectcount-1)/WIDTH][(rectcount-1)%WIDTH]!=1)
		{
			if(close_list.Search(rectcount-1) == 0)
			{
				if(open_list.Search(rectcount-1) == 0)
				{
					rect[rectcount-1].pre = &rect[rectcount];
					rect[rectcount-1].h_value = get_h_value(rectcount-1);
					rect[rectcount-1].g_value = get_g_value(rectcount-1);
					open_list.Insert(open_list.Length(),rectcount-1);
				}
				else
				{
					if(rect[rectcount].g_value + 10 < rect[rectcount-1].g_value)
					{
						rect[rectcount-1].pre = &rect[rectcount];
						rect[rectcount-1].g_value = get_g_value(rectcount-1);
					}
				}
			}
		}
	}
	return Find();
}

int Astart::get_h_value(int i)
{
	return ((abs(end/WIDTH - i/WIDTH) + abs(end%WIDTH - i%WIDTH)) * 10);
}

int Astart::get_g_value(int i)
{
	return (rect[i].pre->g_value + 10);
}

void Astart::GetResult()
{
	Rect *p = &rect[end];
	while(p != NULL)
	{
		value_list.Insert(value_list.Length(),*p);
		p = p->pre;
	}
}