Dirty little Alchemist - Brauche Suchalgorithmus

[Pyro Phoenix]

Ich finde das Alchemiesystem in Skyrim recht interessant. Insbesondere interessiert mich, wieviele und welche Effekte man mit einem Trank erzielen kann. Darum hab ich mich mal ran gesetzt und ein kleines Konsolenprogramm gebastelt. Nu komm ich aber nicht weiter, weil ich einfach keine Ahnung von Algorithmen habe. Deswegen brauch ich eure Hilfe.

Für die erfolgreiche Erstellung von Tränken gilt:

- Minimal 2 Zutaten pro Trank.
- Maximal 3 Zutaten pro Trank.
- Jede Zutat hat 4 verschiedene Effekte.
- Um Erfolgreich einen Effekt in einen Trank zu übernehmen, benötigt man zwei identische Wirkungen.

Die theoretische Anzahl beträgt also maximal 6 Effekte pro Trank.

Die Zutaten lade ich aus einer CSV in eine Liste - Die Struktur schaut folgendermaßen aus:

struct s_ingItem
{
	char				ingName[256];
	int					ingEffect[4];
	float				ingWeight;
	float				ingValue;
	struct s_ingItem	*p_next;
	struct s_ingItem	*p_last;
};

Wie geht man das Ganze jetzt am Besten an ?

[314159265358979]

Pyro Phoenix schrieb:

Wie geht man das Ganze jetzt am Besten an ?

Wie geht man was jetzt am Besten an?

[Pyro Phoenix]

Ich weiß nicht, wie ich das

wieviele und welche Effekte man mit einem Trank erzielen kann

programmiertechnisch realisieren soll.

[cooky451]

Dazu brauchste erst mal eine Datenbank (a.k.a. Textdatei) mit allen Zutaten und den zugehörigen Effekten. Hast du die? Dann alles einlesen in einen std::vector<Zutaten> und alle zweier und alle dreier Kombinationen auf "geeignet" testen. Wenn du dann alle als geeignet getesteten Kombinationen in eine andere Textdatei ausgibst, hast du alle Tränke des Spiels.

[Pyro Phoenix]

Jopp - die Idee kam mir auch grade (Nikotin sei dank :D)

Ich gehe also nacheinander alle Zutaten in Dreiermengen durch, und überprüfe, ob dabei ein "gültiger" Trank produziert wurde. Wenn ja, "notiere" ich die Kombination zusammen mit den erzielten Effekten. Wenn die dritte Zutat keinen weiteren Effekt bringt, streiche ich sie heraus, um sie nicht zu verschwenden. Wenn die zweite Zutat ebenfalls keinen Effekt erzielt, ist die Kombination nutzlos und wird nicht notiert.

War das wirklich so "einfach", oder gibts da noch irgendeinen Fallstrick ?

[314159265358979]

Pyro Phoenix schrieb:

Nikotin sei dank

Stirb. BITTE.

[icarus2]

314159265358979 schrieb:

Stirb. BITTE.

???

[Pyro Phoenix]

Danke für eure Mithilfe - ich werd mich bei konkreteren Umsetzungsproblemen hier sicher noch mal zu Worte melden.

314159265358979 schrieb:

Pyro Phoenix schrieb:

Nikotin sei dank

Stirb. BITTE.

Nein, den Gefallen werde ich dir nicht tun. Dafür rauche ich eindeutig zu selten :p

icarus2 schrieb:

314159265358979 schrieb:

Stirb. BITTE.

???

Ka. Ich glaub, er mag mich nicht

[Benutzername123]

Pyro Phoenix schrieb:

icarus2 schrieb:

314159265358979 schrieb:

Stirb. BITTE.

???

Ka. Ich glaub, er mag mich nicht

Wie passend, ihn mag hier auch niemand.

[Pyro Phoenix]

So. Ich habs geschafft. Das Programm arbeitet wie gewünscht. Allerdings nur innerhalb der IDE. Wenn ich das Programm direkt über den Explorer starte, stürzt es ab. Ich vermute, ich habe irgendwo einen groben Fehler beim Umgang mit den Pointern gemacht. Könnt ihr mir da ein wenig auf die Sprünge helfen ?

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

struct s_ingItem
{
	char				*ingName;
	int					ingEffect[4];
	float				ingWeight;
	int					ingValue;
	struct s_ingItem	*p_next;
	struct s_ingItem	*p_last;
};

int initItem (s_ingItem *p_actvItem)
{
	p_actvItem->ingName				= NULL;
	for (int i = 0; i <= 3; i++)
		p_actvItem->ingEffect[i]	= NULL;
	p_actvItem->ingWeight			= NULL;
	p_actvItem->ingValue			= NULL;
	p_actvItem->p_last				= NULL;
	p_actvItem->p_next				= NULL;

	return 0;
}

struct s_validRecipe
{
	char					*ingName[3];
	int						ingEffect[6];
	struct s_validRecipe	*p_next;
	struct s_validRecipe	*p_last;
};

int initRecipe (s_validRecipe *p_actvRecipe)
{
	for (int i = 0; i <= 2; i++)
		p_actvRecipe->ingName[i]	= NULL;
	for (int i = 0; i <= 5; i++)
		p_actvRecipe->ingEffect[i]	= NULL;
	p_actvRecipe->p_next			= NULL;
	p_actvRecipe->p_last			= NULL;

	return 0;
}

int addEffect (s_validRecipe *p_actvRecipe, int effect)
{
	for (int i = 0; i <= 5; i++)
		if (p_actvRecipe->ingEffect[i] == effect)
			return 0;

	for (int i = 0; i <= 5; i++)
		if (p_actvRecipe->ingEffect[i] == NULL)
		{
			p_actvRecipe->ingEffect[i] = effect;
			break;
		}

	return 1;
}

int addName (s_validRecipe *p_actvRecipe, char *name)
{
	for (int i = 0; i <= 2; i++)
		if (p_actvRecipe->ingName[i] == name)
			return 0;

	for (int i = 0; i <= 2; i++)
		if (p_actvRecipe->ingName[i] == NULL)
		{
			p_actvRecipe->ingName[i] = name;
			break;
		}

	return 1;
}

int checkDuplicates (s_validRecipe *p_actvRecipe) // When duplicate is found, clear out the active recipe.
{
	s_validRecipe *p_iterateRecipe;

	p_iterateRecipe = p_actvRecipe->p_last;

	while (p_iterateRecipe != NULL)
	{
		if ((p_actvRecipe->ingName[0] == p_iterateRecipe->ingName[0]) && (p_actvRecipe->ingName[1] == p_iterateRecipe->ingName[1]) && (p_actvRecipe->ingName[2] == p_iterateRecipe->ingName[2]))
		{
			for (int i = 0; i <= 2; i++)
				p_actvRecipe->ingName[i]	= NULL;
			for (int i = 0; i <= 5; i++)
				p_actvRecipe->ingEffect[i]	= NULL;
			p_actvRecipe->p_next			= NULL;
			return 1;
		}
		else
			p_iterateRecipe = p_iterateRecipe->p_last;
	};
	return 0;
}

int main (int argc, char *argv[], char *envp[])
{
	printf ("Dirty little Alchemist (Version 1)\nWill calculate all possible potions in Skyrim. Modifiable database included !\n\t-by LucidDream 2011\n\n");

	int count = 1;

	s_ingItem		*p_ingListRoot;

	p_ingListRoot			= (s_ingItem*) malloc (sizeof(s_ingItem));
	initItem (p_ingListRoot);

	s_ingItem *p_ingListActv = p_ingListRoot; // Create and set active pointer to root node.

	FILE *pF_ingredients;
	pF_ingredients = NULL;

	pF_ingredients = fopen("Ingredients.csv", "rb");

	if (pF_ingredients == NULL)
	{
		perror("Error opening file \"Ingredients.csv\"");
		return 1;
	}

	printf ("Found Database.\n");

	while (!feof(pF_ingredients)) // Start parsing the CSV
	{
		p_ingListActv->ingName	= (char*) malloc (sizeof(char));
		fscanf(pF_ingredients,"%[^;];", p_ingListActv->ingName);
		for (int i = 0; i <= 3; i++)
			fscanf(pF_ingredients,"%i;", &p_ingListActv->ingEffect[i]);
		fscanf(pF_ingredients,"%f;", &p_ingListActv->ingWeight);
		fscanf(pF_ingredients,"%i\n", &p_ingListActv->ingValue);

		if (!feof(pF_ingredients))
		{	
			p_ingListActv->p_next = (s_ingItem*) malloc (sizeof(s_ingItem));
			initItem (p_ingListActv->p_next);
			p_ingListActv->p_next->p_last = p_ingListActv;
			p_ingListActv = p_ingListActv->p_next;
		}
		printf ("Reading Data: %i Ingredients identified\r", count);
		count++;
	};

	printf ("\n");
	count = 1;

	fclose (pF_ingredients);

	// Done with importing Data - ready for the Magic !

	s_ingItem *p_ingListIng1		= p_ingListRoot;			// First ingredient
	s_ingItem *p_ingListIng2		= p_ingListRoot->p_next;	// Second ingredient
	s_ingItem *p_ingListIng3		= p_ingListIng2->p_next;	// Third ingredient

	s_validRecipe *p_recipeListRoot	= (s_validRecipe*) malloc (sizeof(s_validRecipe));
	initRecipe (p_recipeListRoot);
	s_validRecipe *p_recipeListActv	= p_recipeListRoot;

	do
	{
		for (int ing1 = 0; ing1 <= 3; ing1++)
		{
			for (int ing2 = 0; ing2 <= 3; ing2++)
			{
				for (int ing3 = 0; ing3 <= 3; ing3++)
				{
					if (p_ingListIng1->ingEffect[ing1] == p_ingListIng3->ingEffect[ing3])
					{
						addName(p_recipeListActv, p_ingListIng1->ingName);
						addName(p_recipeListActv, p_ingListIng3->ingName);
						addEffect(p_recipeListActv, p_ingListIng1->ingEffect[ing1]);
					}
					if (p_ingListIng1->ingEffect[ing1] == p_ingListIng2->ingEffect[ing2])
					{
						addName(p_recipeListActv, p_ingListIng1->ingName);
						addName(p_recipeListActv, p_ingListIng2->ingName);
						addEffect(p_recipeListActv, p_ingListIng2->ingEffect[ing2]);
					}
					if (p_ingListIng2->ingEffect[ing2] == p_ingListIng3->ingEffect[ing3])
					{
						addName(p_recipeListActv, p_ingListIng2->ingName);
						addName(p_recipeListActv, p_ingListIng3->ingName);
						addEffect(p_recipeListActv, p_ingListIng3->ingEffect[ing3]);
					}
				}
			}
		}

		if (p_ingListIng3->p_next != NULL) // Pass throuh ingredients
			p_ingListIng3 = p_ingListIng3->p_next;
		else
		{
			if (p_ingListIng2->p_next != p_ingListIng3)
			{
				p_ingListIng2 = p_ingListIng2->p_next;
				p_ingListIng3 = p_ingListIng2->p_next;
			}
			else
			{
				if (p_ingListIng1->p_next != p_ingListIng2)
				{
					p_ingListIng1 = p_ingListIng1->p_next;
					p_ingListIng2 = p_ingListIng1->p_next;
				}
				else
					break; // Exit loop, when end of list is reached.
			}
		}

		if (p_recipeListActv->ingName[0] != NULL) // Was a new Potion found ?
		{
			if (!checkDuplicates(p_recipeListActv)) // If this Potion is not listed ...
			{
				printf ("Calculating: %i Valid Potions Found\r", count); 
				p_recipeListActv->p_next = (s_validRecipe*) malloc (sizeof(s_validRecipe)); // ... Add an empty entry.
				initRecipe (p_recipeListActv->p_next);
				p_recipeListActv->p_next->p_last = p_recipeListActv;
				p_recipeListActv = p_recipeListActv->p_next;
				count ++;
			}			
		}

	} while (1);

	printf ("\n");
	count = 1;

	// Magic is over. Now generate the valid potions list.

	FILE *pF_recipeList;
	pF_recipeList = NULL;

	pF_recipeList = fopen ("Valid Recipes.csv", "w+");

	if ( pF_recipeList == NULL )
	{
		perror("Error createing / writing to file \"Valid Recipes.csv\"");
		return 1;
	}

	p_recipeListActv = p_recipeListRoot;

	do
	{
		for (int i = 0; i <= 2; i++)
		{
			if (p_recipeListActv->ingName[i] != NULL && i == 0)
				fprintf (pF_recipeList, "%s", p_recipeListActv->ingName[i]);
			if (p_recipeListActv->ingName[i] != NULL && i != 0)
				fprintf (pF_recipeList, ";%s", p_recipeListActv->ingName[i]);
			if (p_recipeListActv->ingName[i] == NULL)
				fprintf (pF_recipeList, ";");
		}
		for (int i = 0; i <= 5; i++)
		{
			if (p_recipeListActv->ingEffect[i] != NULL)
				fprintf (pF_recipeList, ";%i", p_recipeListActv->ingEffect[i]);
			else
				break;
		}
		fprintf (pF_recipeList, "\n");
		printf ("Write Data: %i Valid recipes saved\r", count);
		count ++;
		p_recipeListActv = p_recipeListActv->p_next;
	} while (p_recipeListActv != NULL);

	fclose (pF_recipeList);

	return 0;
}

Die benötigte Datenbank könnt ihr hier runterladen, falls Interesse daran bestehen sollte: http://www.megaupload.com/?d=GENT7B7M

Bekannte Fehler:
Mir ist klar, dass ich den reservierten Speicher nicht wieder frei gebe
Könnte auch sein, dass der Suchalgorithmus ineffektiv ist und/oder unvollständig arbeitet.
Ich muss an meiner Kommentierung arbeiten.

[cooky451]

Ich wollte dir gerade sagen, dass du es mit C++ so viel leichter haben könntest - und dann sehe ich "new" und "true". Das soll nicht ernsthaft C++ sein oder?

[Pyro Phoenix]

Im Grunde genommen ist es weder das eine, noch das andere. Aber es erfüllt seinen Zweck - so halbwegs zumindest.

[Ethon]

Ich finde das Alchemiesystem in Skyrim recht interessant.

Das Alchemiesystem von M-O-R-R-O-W-I-N-D. Morrowind.
Das wo sämtliche Story und Kreatives für Skyrim und Oblivion herkommt.

[Pyro Phoenix]

So, hab das Ganze auf ANSI-C C99 umgeschrieben. Probleme gibts mit Zeile 140.