AI 2008 FLD2 & Pathfinding

Wrote new code? Fixed a bug? Want to discuss technical stuff? Feel free to post it here.

Moderator: Moderators

Message
Author
sli
Perl Monk
Perl Monk
Posts: 810
Joined: 04 Apr 2008, 17:26
Noob?: No

Re: FLD2 proposal [for the future]

#31 Post by sli »

Fields are only processed when being generated. If we simply add in the code for generating a dist file in the gat2fld2 script to increase weights near walls, Kore would only need to load the field and be done. Something else that would be nice would be some sort of metadata containing locations of points of interest. Specifically snipable cliffs and walkable water. The latter would be difficult and might slow things down, however, but fuck me if it wouldn't be handy. The easiest way would be to just create rectangles (as in, 8 bytes of data that creates an entire block of coords that are walkable water) that are 100% walkable water. I'm not sure how snipable cliffs would be handled, we might have to just bolster the pathfinding for that to create a LOS over the cliff.

Just some thoughts.
cs : ee : realist

Cozzie
Spam Generator
Spam Generator
Posts: 499
Joined: 04 Apr 2008, 09:30
Noob?: No
Location: Melbourne, City of beer and awful sushis

Re: FLD2 proposal [for the future]

#32 Post by Cozzie »

This is a band aid solution, why not code it so that the bot decides itself?
Make Openkore Awesome. Join the team.

sli
Perl Monk
Perl Monk
Posts: 810
Joined: 04 Apr 2008, 17:26
Noob?: No

Re: FLD2 proposal [for the future]

#33 Post by sli »

Well I figure that certain flags are walkable and others are not, the FLD could be fed into A* for routing and just know that certain flags are certain weights, e.g. normal land is 1, walkable water is 1, walls are 255, areas near walls are moderately high, etc.
cs : ee : realist

Motivus
Developers
Developers
Posts: 157
Joined: 04 Apr 2008, 13:33
Noob?: Yes

Re: FLD2 proposal [for the future]

#34 Post by Motivus »

sli wrote:Well I figure that certain flags are walkable and others are not, the FLD could be fed into A* for routing and just know that certain flags are certain weights, e.g. normal land is 1, walkable water is 1, walls are 255, areas near walls are moderately high, etc.
Yes, A* should handle basic weighting like that.

The largest hurdle in OpenKore's pathing is the lack of code (any code) to support intelligent micro movements. OpenKore has great macro movement, like moving across the world or picking a far away point on the map. It even has great pathing when it comes to casually walking around a map. It falls flat for any movement involving fighting, dynamic tiles (area skills/monster attack range, portals), or anything that doesn't involve going from a fld-determined point a to b with dist weighting.

I've casually thought about the solution for a while, but it's hard to just pull the solution out of thin air with no testing or previous experience. The hardest part is probably dealing with moving monsters or area skills that are in the process of being cast. I think we can afford to use perl to calculate it, but at the same time it would be more efficient to just pass relevant data to A* and call a different pathing function. Which opens an entirely new problem, how do you make a potential ton of information available to an external dll efficiently?

The math/code to properly do these things isn't all that hard. I've laid out the basics of the math before, and adapting that to code isn't too hard to do. What is hard to do is to come up with something efficient using the restraints of the project.

A "global" path function that returns an array like we do now, and then you call a "local" path to get from the already pathed A->B (and possibly don't end up on B). An additional function to get the closest LoS tile would be nice, too, for attacking things with ranged characters. Despite how advanced Kore's configuration and overall play choices can be, we're still rolling on the hacked together 2002 (or 2003?) blind attack system. Except now it's all modular and pretty or something. The AI has came really far, but the fighting/local pathing hasn't budged.
Oh no.

sli
Perl Monk
Perl Monk
Posts: 810
Joined: 04 Apr 2008, 17:26
Noob?: No

Re: FLD2 proposal [for the future]

#35 Post by sli »

Actually, micro movements are a huge aspect of Erok that I've been keeping to myself for a while. I've been studying A* implementation to create one that learns based on its environment. This will make routing more random by temporarily avoiding areas where the bot has already been, and routing around things like monster skills, traps, etc. It's not as hard as it seems, you just increase weights for a short period, five minutes or so, then drop them back down. Avoiding area skills will just be for the duration of routing around it. If a Magnolia places a trap on tile 132,74 (or whatever), then I just do something like this:

Code: Select all

# python pseudocode

field[132][74]['real_weight'] = field[132][74]['weight']
field[132][74]['weight'] = 255
AI.route()
field[132][74]['weight'] = field[132][74]['real_weight']
del field[132][74]['real_weight']
cs : ee : realist

Technology
Super Moderators
Super Moderators
Posts: 801
Joined: 06 May 2008, 12:47
Noob?: No

Re: FLD2 proposal [for the future]

#36 Post by Technology »

One ST0 to rule them all? One PE viewer to find them!
One ST_kRO to bring them all and in the darkness bind them...

Mount Doom awaits us, fellowship of OpenKore!

jsteng
Noob
Noob
Posts: 11
Joined: 04 Jul 2008, 10:39
Noob?: No

Re: AI 2008 FLD2 & Pathfinding

#37 Post by jsteng »

Its been many years since I stopped programming for Kore, so I am not certain if my information is still accurate. so here goes anyways:

The original A* codes are with tools.dll; but I believed OpenKore came up with it's own A* Pathfinding dll or so that incorporated the "wall avoiding" codes and does what it is supposedly advertised; I personally do not use that but understand that the implementation was simply to put heavier weights on the squares nearer walls making them costs more to travel and thus avoiding it. However, the actual walking, which is still issued by Kore's sendmove routine:

sendmove (x,y) will move the bot from your current location to the next destination specified by (x,y) coordinate and this itself does not avoid wall - just the most efficient path, as dictated by the game server's pathing codes.

The original tools.dll has very minimal functionality to it. it gives only a path of coordinates from point A to point B. Based on the discussion above, it appears to me that what you need are additional functions into the tools.dll that will be used to provide "walkable path" (to be used for walking), "LoS path" (to be used for sniping arrows/throw/spells).

You will need these 2 functions separated or you will end up with a heavy code trying to do two things.
It is possible to just use 1 code BUT feeding it with a different MAP data. Feed tools.dll with the original FLD file for walking and feed it with this FLD2 map for the snipables. this solution isnt elegant - requiring you to have 2 map files and another source of HD space..... but hey, you can still put kore in a $5 4GB memory stick with plenty to spare..

Henrybk
Developers
Developers
Posts: 11
Joined: 15 Mar 2011, 22:50
Noob?: No

Re: AI 2008 FLD2 & Pathfinding

#38 Post by Henrybk »

Ultimate 5 years, 11 months and 13 days topic revive. Hi guys, i've been working on a new code for the openkore pathfinding for the past 3 weeks and today i finally completed it (or so do I think), it is written in C, even though i haven't implemented it in kore itself it has shown good work.

The code itself:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define DIAGONAL 14
#define ORTOGONAL 10
#define NONE 0
#define OPEN 1
#define CLOSED 2
#define PATH 3
#define LCHILD(currentIndex) 2 * currentIndex + 1
#define RCHILD(currentIndex) 2 * currentIndex + 2
#define PARENT(currentIndex) (int)floor((currentIndex - 1) / 2)

typedef struct Nodes{
    unsigned short x;
    unsigned short y;
    unsigned short parentX;
    unsigned short parentY;
	unsigned int whichlist : 2;
	unsigned int openListIndex;
	unsigned int g;
	unsigned short h;
	unsigned int f;
} Node;

typedef struct Blocks{
	unsigned int walkable : 1;
	unsigned int water : 1;
	unsigned int snipleable : 1;
	unsigned int cliff : 1;
	Node nodeInfo;
} Block;

typedef struct Maps{
	unsigned int height;
	unsigned int width;
	Block **grid;
} Map;

typedef struct {
    int x;
    int y;
    int distanceFromCurrent;
} eachNeigh;

typedef struct {
    eachNeigh neighborNodes[8];
    int count;
} Neighbors;

typedef struct {
    int x;
    int y;
    int f;
} TypeList;

void freeMap(Map* currentMap){
    int i;
    for(i = 0; i < currentMap->height; i++);{
        free(currentMap->grid[i]);
    }
    free(currentMap->grid);
    free(currentMap);
}

Map* mallocMap(int width, int height){
    Map* currentMap = (Map*) malloc(sizeof(Map));
    currentMap->width = width;
	currentMap->height = height;
	currentMap->grid = (Block**) malloc(currentMap->width * sizeof(Block*));
	int j;
	for(j = 0; j < currentMap->width; j++){
        currentMap->grid[j] = (Block*) malloc(currentMap->height * sizeof(Block));
    }
    return currentMap;
}

Map* GenerateMap(char *field){
	FILE *fp = fopen(field, "rb");
	int width = fgetc(fp) + fgetc(fp) * 256;
	int height = fgetc(fp) + fgetc(fp) * 256;
    Map* currentMap = mallocMap(width, height);

	int x = 0;
	int y = 0;
	int i;
	while ((i = fgetc(fp)) != EOF) {
		currentMap->grid[x][y].walkable = (i & 1) ? 1 : 0;
		currentMap->grid[x][y].snipleable = (i & 2) ? 1 : 0;
		currentMap->grid[x][y].water = (i & 4) ? 1 : 0;
		currentMap->grid[x][y].cliff = (i & 8) ? 1 : 0;
		currentMap->grid[x][y].nodeInfo.whichlist = NONE;
        currentMap->grid[x][y].nodeInfo.openListIndex = NONE;
		if (x == currentMap->width - 1) {
			y++;
			x = 0;
		}
		else {
			x++;
		}
	}
	fclose(fp);
	return currentMap;
}

int heuristic_cost_estimate(Node* currentNode, Node* goalNode)
{
	int xDistance = abs(currentNode->x - goalNode->x);
	int yDistance = abs(currentNode->y - goalNode->y);
	int hScore;
	if (xDistance > yDistance) {
		hScore = DIAGONAL * yDistance + ORTOGONAL * (xDistance - yDistance);
	}
	else {
		hScore = DIAGONAL * xDistance + ORTOGONAL * (yDistance - xDistance);
	}
	return hScore;
}

void organizeNeighborsStruct(Neighbors* currentNeighbors, Node* currentNode, Map* currentMap)
{
    int count = 0;
    int i;
	for (i = -1; i <= 1; i++)
	{
	    int j;
		for (j = -1; j <= 1; j++)
		{
			if (i == 0 && j == 0){ continue; }
			int x = currentNode->x + i;
			int y = currentNode->y + j;
			if (x > currentMap->width - 1 || y > currentMap->height - 1){ continue; }
			if (x < 0 || y < 0){ continue; }
			if (currentMap->grid[x][y].walkable == 0){ continue; }
			if (i != 0 && j != 0) {
                if (currentMap->grid[x][currentNode->y].walkable == 0 || currentMap->grid[currentNode->x][y].walkable == 0){ continue; }
                currentNeighbors->neighborNodes[count].distanceFromCurrent = DIAGONAL;
			} else {
                currentNeighbors->neighborNodes[count].distanceFromCurrent = ORTOGONAL;
			}
				currentNeighbors->neighborNodes[count].x = x;
				currentNeighbors->neighborNodes[count].y = y;
				count++;
		}
	}
	currentNeighbors->count = count;
}

//Openlist is a binary heap of min-heap type

void openListAdd (TypeList* openList, Node* infoAdress, int openListSize, Map* currentMap)
{
    openList[openListSize].x = infoAdress->x;
    openList[openListSize].y = infoAdress->y;
    openList[openListSize].f = infoAdress->f;
    currentMap->grid[openList[openListSize].x][openList[openListSize].y].nodeInfo.openListIndex = openListSize;
    int currentIndex = openListSize;
    TypeList Temporary;
    while (PARENT(currentIndex) >= 0) {
        if (openList[PARENT(currentIndex)].f > openList[currentIndex].f) {
            Temporary = openList[currentIndex];
            openList[currentIndex] = openList[PARENT(currentIndex)];
            currentMap->grid[openList[currentIndex].x][openList[currentIndex].y].nodeInfo.openListIndex = currentIndex;
            openList[PARENT(currentIndex)] = Temporary;
            currentMap->grid[openList[PARENT(currentIndex)].x][openList[PARENT(currentIndex)].y].nodeInfo.openListIndex = PARENT(currentIndex);
            currentIndex = PARENT(currentIndex);
        } else { break; }
    }
}

void reajustOpenListItem (TypeList* openList, Node* infoAdress, int openListSize, Map* currentMap)
{
    int currentIndex = infoAdress->openListIndex;
    openList[currentIndex].f = infoAdress->f;
    TypeList Temporary;
    while (PARENT(currentIndex) >= 0) {
        if (openList[PARENT(currentIndex)].f > openList[currentIndex].f) {
            Temporary = openList[currentIndex];
            openList[currentIndex] = openList[PARENT(currentIndex)];
            currentMap->grid[openList[currentIndex].x][openList[currentIndex].y].nodeInfo.openListIndex = currentIndex;
            openList[PARENT(currentIndex)] = Temporary;
            currentMap->grid[openList[PARENT(currentIndex)].x][openList[PARENT(currentIndex)].y].nodeInfo.openListIndex = PARENT(currentIndex);
            currentIndex = PARENT(currentIndex);
        } else { break; }
    }
}

Node* openListGetLowest (TypeList* openList, Map* currentMap, int openListSize)
{
    printf("Now starting openListGetLowest %d\n", openList[0].f);
    Node* lowestNode = &currentMap->grid[openList[0].x][openList[0].y].nodeInfo;
    openList[0] = openList[openListSize-1];
    currentMap->grid[openList[0].x][openList[0].y].nodeInfo.openListIndex = 0;
    int lowestChildIndex = 0;
    int currentIndex = 0;
    TypeList Temporary;
    while (LCHILD(currentIndex) < openListSize - 2) {
        //There are 2 children
        if (RCHILD(currentIndex) <= openListSize - 2) {
            if (openList[RCHILD(currentIndex)].f <= openList[LCHILD(currentIndex)].f) {
                lowestChildIndex = RCHILD(currentIndex);
            } else {
                lowestChildIndex = LCHILD(currentIndex);
            }
        } else {
            //There is 1 children
            if (LCHILD(currentIndex) <= openListSize - 2) {
                lowestChildIndex = LCHILD(currentIndex);
            } else {
                break;
            }
        }
        if (openList[currentIndex].f > openList[lowestChildIndex].f) {
            Temporary = openList[currentIndex];
            openList[currentIndex] = openList[lowestChildIndex];
            currentMap->grid[openList[currentIndex].x][openList[currentIndex].y].nodeInfo.openListIndex = currentIndex;
            openList[lowestChildIndex] = Temporary;
            currentMap->grid[openList[lowestChildIndex].x][openList[lowestChildIndex].y].nodeInfo.openListIndex = lowestChildIndex;
            currentIndex = lowestChildIndex;
        } else { break; }
    }
    return lowestNode;
}

void reconstruct_path(Map* currentMap, Node* startNode, Node* currentNode)
{
	int i = 0;
	printf("Building Path from %d-%d to %d-%d\n", currentNode->x, currentNode->y, startNode->x, startNode->y);
	while (currentNode->x != startNode->x || currentNode->y != startNode->y)
    {
        printf("Step %d : %d-%d\n", i, currentNode->x, currentNode->y);
        currentMap->grid[currentNode->parentX][currentNode->parentY].nodeInfo.whichlist = PATH;
        currentNode = &currentMap->grid[currentNode->parentX][currentNode->parentY].nodeInfo;
        i++;
    }
    printf("Destination reached at step %d\n", i);
}

void Pathfind (Node* startNode, Node* goalNode, Map* currentMap)
{
    printf("We have to go from %d-%d to %d-%d\n", startNode->x, startNode->y, goalNode->x, goalNode->y);
    int size = currentMap->height * currentMap->width;
    int openListSize = 1;
    int Gscore = 0;
    int indexNeighbor = 0;
    int nodeList;
    TypeList* openList = (TypeList*) malloc(size * sizeof(TypeList));
    Node* currentNode;
    openList[0].x = startNode->x;
    openList[0].y = startNode->y;
    currentMap->grid[openList[0].x][openList[0].y].nodeInfo.x = startNode->x;
    currentMap->grid[openList[0].x][openList[0].y].nodeInfo.y = startNode->y;
    Neighbors* currentNeighbors = (Neighbors*) malloc(sizeof(Neighbors));
    Node* infoAdress;
    while (openListSize > 0) {
        //get lowest F score member of openlist and delete it from it
        currentNode = openListGetLowest (openList, currentMap, openListSize);
        openListSize--;
        printf("We are at %d-%d\n", currentNode->x, currentNode->y);
        printf("Now openlist is %d nodes long\n", openListSize);

        //add currentNode to closedList
        currentNode->whichlist = CLOSED;

		//if current is the goal, return the path.
		if (currentNode->x == goalNode->x && currentNode->y == goalNode->y) {
            //return path
            printf("OVER\n");
            reconstruct_path(currentMap, startNode, currentNode);
			break;
		}

		//add current to closedset.



		organizeNeighborsStruct(currentNeighbors, currentNode, currentMap);
		for (indexNeighbor = 0; indexNeighbor < currentNeighbors->count; indexNeighbor++) {
            infoAdress = &currentMap->grid[currentNeighbors->neighborNodes[indexNeighbor].x][currentNeighbors->neighborNodes[indexNeighbor].y].nodeInfo;
            printf("Checking neighbor of %d-%d at location %d-%d\n", currentNode->x, currentNode->y, currentNeighbors->neighborNodes[indexNeighbor].x, currentNeighbors->neighborNodes[indexNeighbor].y);
			nodeList = infoAdress->whichlist;
			if (nodeList == CLOSED) { continue; }

			Gscore = currentNode->g + currentNeighbors->neighborNodes[indexNeighbor].distanceFromCurrent;

			if (nodeList != OPEN) {
                printf("Adding node to Openlist\n");
                infoAdress->x = currentNeighbors->neighborNodes[indexNeighbor].x;
                infoAdress->y = currentNeighbors->neighborNodes[indexNeighbor].y;
                infoAdress->parentX = currentNode->x;
                infoAdress->parentY = currentNode->y;
                infoAdress->whichlist = OPEN;
                infoAdress->g = Gscore;
                infoAdress->h = heuristic_cost_estimate(infoAdress, goalNode);
                infoAdress->f = Gscore + infoAdress->h;
				openListAdd (openList, infoAdress, openListSize, currentMap);
				openListSize++;
                printf("Now openlist is %d nodes long\n", openListSize);
			} else {
                if (Gscore < infoAdress->g) {
                    printf("Reajusting node on Openlist\n");
                    infoAdress->parentX = currentNode->x;
                    infoAdress->parentY = currentNode->y;
                    infoAdress->g = Gscore;
                    infoAdress->f = Gscore + infoAdress->h;
                    reajustOpenListItem (openList, infoAdress, openListSize, currentMap);
                }
			}
		}
	}
	printf("After While\n");
    free(openList);
}

void PrintMap(Map* currentMap){
	FILE *block = fopen("printedMap.txt", "w");
	int tx = 0;
	int ty = currentMap->height - 1;
	int size = currentMap->width*currentMap->height;
	char walkable = ' ';
	char unwalkable = '#';
	char openList = 'c';
	char closedList = '.';
	char path = '0';
	int j;
	for (j = 0; j < size; j++)
	{
		fprintf(block, "%c", currentMap->grid[tx][ty].walkable ? currentMap->grid[tx][ty].nodeInfo.whichlist == 3? path : currentMap->grid[tx][ty].nodeInfo.whichlist == 2? closedList : currentMap->grid[tx][ty].nodeInfo.whichlist == 1? openList : walkable : unwalkable);
		if (tx == currentMap->width - 1) {
			ty--;
			tx = 0;
			fprintf(block, "\n");
		}
		else {
			tx++;
		}
	}
	fclose(block);
}

int main(){
	Map* currentMap = GenerateMap("mapas\\hugel.fld2");
	int startX = 83;
	int startY = 57;
	currentMap->grid[startX][startY].nodeInfo.x = startX;
	currentMap->grid[startX][startY].nodeInfo.y = startY;
	currentMap->grid[startX][startY].nodeInfo.g = 0;
	int endX = 211;
	int endY = 234;
	currentMap->grid[endX][endY].nodeInfo.x = endX;
	currentMap->grid[endX][endY].nodeInfo.y = endY;
	Pathfind(&currentMap->grid[startX][startY].nodeInfo, &currentMap->grid[endX][endY].nodeInfo, currentMap);
	PrintMap(currentMap);
	freeMap(currentMap);
	return 0;
}
It is my first code in C so it problably is a lot messy but it uses the new FLD2 format instead of dist and fld files, and is guaranteed to find the shortest path between two points.

Also here is the modified fld to fld2 converter that i used:

Code: Select all

#!/usr/bin/perl
# See http://www.openkore.com/wiki/index.php/Field2_file_format
# for information about the file formats.
# fld_to_fld2
use strict;
use constant {
	TILE_NOWALK => 0,
	TILE_WALK => 1,
	TILE_SNIPE => 2,
	TILE_WATER => 4,
	TILE_CLIFF => 8,
};

# conversion (ex. $TILE_TYPE[0] = TILE_WALK = 1), (ex. $TILE_TYPE[1] = TILE_NOWALK = 0)
my @TILE_TYPE = (	TILE_WALK,				# 0) Walkable
					TILE_NOWALK,			# 1) Non-walkable
					TILE_WATER,				# 2) Non-walkable water (not snipable)
					TILE_WALK|TILE_WATER,	# 3) Walkable water
					TILE_WATER|TILE_SNIPE,	# 4) Non-walkable water (snipable)
					TILE_CLIFF|TILE_SNIPE,	# 5) Cliff (snipable)
					TILE_CLIFF);			# 6) Cliff (not snipable)


my $i = 0;
foreach my $name (sort(listMaps("."))) {
	$i++;
	fld_to_fld2("$name.fld", "$name.fld2");
}

sub listMaps {
	my ($dir) = @_;
	my $handle;

	opendir($handle, $dir);
	my @list = grep { /\.fld$/i && -f $_ } readdir $handle;
	closedir $handle;

	foreach my $file (@list) {
		$file =~ s/\.fld$//i;
	}
	return @list;
}
##
# void fld_to_fld2(String fld, String fld2)
#
# Convert a .FLD file to the specified .FLD2 file.
sub fld_to_fld2 {
	my ($fld, $fld2) = @_;
	my ($in, $out, $data);

	if (!open $in, "<", $fld) {
		print "Cannot open $fld for reading.\n";
		exit 1;
	}
	if (!open $out, ">", $fld2) {
		print "Cannot open $fld2 for writing.\n";
		exit 1;
	}

	binmode $in;
	binmode $out;

	# Read fld header.
	read($in, $data, 4);
	my ($width, $height) = unpack("v2", $data);
	my $size = $width * $height;
	# when y = height, we variate x from 0 to width
	# thus, we variate block offset from size - width to size
	my $max_Y = $size - $width;

	print $out pack ("v2", $width, $height);
	my ($y, $x) = (0, 0);
	while (read($in, $data, 1)) {
		my $type = unpack("C", $data);
		# warn us for unknown/new block types
		if ($type > $#TILE_TYPE) {
			print "An unknown blocktype ($type) was found, please report this to the OpenKore devs.\n";
			exit 1;
		# make outter block unwalkable
		} else {
			print $out pack("C", $TILE_TYPE[$type]);
		}
		if ($x == $width-1) {
			$y++;
			$x = 0;
		} else {
			$x++;
		}
	}
	close $in;
	close $out;
}
I changed a little bit to fit better after i found out that maps in ragnarok all are from 0 to height-1/width-1, and that the outer cells can be walkable if set to.

Here are some tests that i made:

On prontera:
Image

On hugel:
Image


On ice_dun03:
Image


The diferent greyscales are from the printMap function, which actually just prints in a text file one character per cell on the map.

The white parts on the images are the non opened walkable cells, the dark ones are the unwalkable cells (aka walls), the grey ones are the cell in the closed list and the black line is the path found.

The code is not complete and still has to be adapted to kore, it just opens the given fld2 map on dir "mapas" and calculates the route from startX/startY to endX/endY (all given in main())

Sorry for the possible bad code.

User avatar
kLabMouse
Administrator
Administrator
Posts: 1301
Joined: 24 Apr 2008, 12:02

Re: AI 2008 FLD2 & Pathfinding

#39 Post by kLabMouse »

Henrybk wrote:Ultimate 5 years, 11 months and 13 days topic revive. Hi guys, i've been working on a new code for the openkore pathfinding for the past 3 weeks and today i finally completed it (or so do I think), it is written in C, even though i haven't implemented it in kore itself it has shown good work.
-===

The diferent greyscales are from the printMap function, which actually just prints in a text file one character per cell on the map.

The white parts on the images are the non opened walkable cells, the dark ones are the unwalkable cells (aka walls), the grey ones are the cell in the closed list and the black line is the path found.

The code is not complete and still has to be adapted to kore, it just opens the given fld2 map on dir "mapas" and calculates the route from startX/startY to endX/endY (all given in main())

Sorry for the possible bad code.
Actually. It's good that someone want to Implement better Path finding and actually have a solution.
Problem here, Is that OpenKore uses vanilla A* a bit or Ray penalty. So it does not walk on walls
On the prontera Map, I've seen a few places, where your algo picked to go beside walls. And also route to target that players normally would not pick.

If you want to implement better path-finding. You should think of making path finder a bit more human-like.

Technology
Super Moderators
Super Moderators
Posts: 801
Joined: 06 May 2008, 12:47
Noob?: No

Re: AI 2008 FLD2 & Pathfinding

#40 Post by Technology »

Henrybk wrote:Ultimate 5 years, 11 months and 13 days topic revive. Hi guys, i've been working on a new code for the openkore pathfinding for the past 3 weeks and today i finally completed it (or so do I think), it is written in C, even though i haven't implemented it in kore itself it has shown good work.
Nice work!
This got me thinking...
Personally I believe that it would benefit Kore tremendously if its current pathfinding & steering were to be abstracted out.
Making this pluggable would lower the threshold for people to experiment with their own algo's and share their POC with others.
One ST0 to rule them all? One PE viewer to find them!
One ST_kRO to bring them all and in the darkness bind them...

Mount Doom awaits us, fellowship of OpenKore!

Post Reply