Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Virex]

Ha ha, unless you're trying to look up anything about Haskell.

Isn't that trivially fixed by using monads?

[Shadowlord]

I mean the function names composed entirely of symbols, of course.

[Virex]

I was trying to make a joke about how the solution to any Haskel problem seems to be "more Monads".

[EnigmaticHat]

BTW, there's only one guide that has ever made A* make enough sense to me so that I could actually implement it, and that's this one.  If you ever want to make a roguelike or something it could help you out.

That's a nice article. About this, though:

8. Dijkstra's Algorithm: While A* is generally considered to be the best pathfinding algorithm (see rant above), there is at least one other algorithm that has its uses - Dijkstra's algorithm. Dijkstra's is essentially the same as A*, except there is no heuristic (H is always 0). Because it has no heuristic, it searches by expanding out equally in every direction. As you might imagine, because of this Dijkstra's usually ends up exploring a much larger area before the target is found. This generally makes it slower than A*.

So why use it? Sometimes we don't know where our target destination is. Say you have a resource-gathering unit that needs to go get some resources of some kind. It may know where several resource areas are, but it wants to go to the closest one. Here, Dijkstra's is better than A* because we don't know which one is closest. Our only alternative is to repeatedly use A* to find the distance to each one, and then choose that path. There are probably countless similar situations where we know the kind of location we might be searching for, want to find the closest one, but not know where it is or which one might be closest.

I think this might be optimized by using H=min(H1,H2,…,Hn) as the heuristic when H1,H2,…,Hn are the heuristics for the targets. Should save a lot of exploration when there's two targets in opposite directions, for instance, by not exploring sidewards.

I believe that if you did that it could result in some pretty incoherent paths.

Imagine you have two targets, one that is close according to the heuristic but actually blocked off by a complicated maze (target A), and one that is far away but unobstructed and thus quicker to reach (target B).  The algorithm will start moving towards A until it hits the maze.  At which point it might randomly hit a tile where the heuristic says B is closer and "lock on" to B.  Alternatively it won't and it will eventually find its way through the maze to A.  In both cases it will produce an inefficient path.  If it gets through the maze then it will be taking a longer than necessary path to reach a target (since it should have gone to B).  However if it hits B things will be even worse as it will make a path that starts going towards A and then "changes its mind" and goes towards B.

[i2amroy]

From what I've heard the best thing to do in a case where you have multiple goals (since dijkstra's can choke performance on larger graphs), is to use a sort of "meta heuristic" on top of the normal heuristic. Start by calculating your heuristic for all possible goal points, and assign the best one as your current "main goal", move towards it, and then subtract the maximum possible amount that your heuristic could decrease for that step from all heuristic values for all goal points as your "meta heuristic" (which is really a super optimistic guess at the path to that particular goal point). Then on each additional step you run your checks on any goals where the "meta heuristic" is a value lower than the actual heuristic, with whichever one having the lowest overall value becoming your new main goal point to move towards.

Note that anything like that is gonna be very expensive to calculate; if this is something you're going to be calculating often over the same area with stable goal points (resource collectors dealing with multiple stable resource collection points, for example) you are probably gonna be best off just precalculating the voronoi diagram for all your different goal points over your given area and then refering to that on each call to determine which is the closest goal for pathfinding to rather than dealing with multiple potential endpoints each time.

[miauw62]

The disadvantage of this in a game is that it makes your pathfinding less predictable to players, though. To take those last two examples as, well, examples, people would probably remark on the little "bump" in the path, especially if this is a very common route.

I don't necessarily disagree with you, but it's still weighing the advantages and the disadvantages. My complaint can, for example, be solved by letting people assign weights to tiles.

The good part about heuristics is that you can adjust the strictness as needed by picking different ones! That particular one was 5 ε IIRC, so if it was slightly too lose for you then you could choose a slomewhat stricter heuristic that, at the cost of additional node checking, would return a path slightly closer to the actual route and smooth that bump right out if you really needed it gone. So in the end you have a heuristic that only checks half as many tiles instead of 1/3rd; it means a fortress that can have twice as many dwarves running before FPS death sets in than with a purely admissible heuristic like manhattan distance.

And there's nothing that says you can't choose a heuristic capable of handling "base weights" that could be preset or player-designated as well; heck, the idea of "Weighting" itself is exactly what heuristics do, they weight certain tiles varying amounts based on their distance from the goal or some other predefined function. Adding an additional input of player weights to let them actually control pathfinding a bit more directly is a pittance to factor in in the vast majority of cases.

A good heuristic can provide massive speedups at the cost of nothing but a little bit of development time and a tiny bit of path regulation (which you can tweak to yourself to reach a point where most people aren't going to be able to tell the difference, and if really necessary you could always add a "player weighting" or "waypoint" system to let players assume direct control of pathfinding if they really depend on it). Sure, it's not that big of a deal if you're running your little test dungeon with 8 units in it. But once you expand that unit count out to 100, or 1000, or 10k (which could be reached in C:DDA with Z-levels on, for example) it starts to matter a bit. Or how about going from 2D to 3D with flying units? That takes your amount needed to check up from n² to n³, and speed will definitely start to matter at that point. So ask yourself the question, which would make the player more excited, having pathfinding that is always the fastest (even when it leads to results that seem counter-intuitive to humans, as mentioned earlier), or having the unit cap be double what it currently is?

(Of course, if you're deadline is tight and you know that you are never really going to be handling more than a few units then by all means feel free to avoid anything more complex than manhattan distance, but pathfinding quickly becomes such a speed critical segment of many programs, and the work/reward ratio is so great for good heuristics, that it's almost always worth it to spend even a little bit of time picking and implementing one.)

Yeah, but for a game like DF, having predictable pathing is a great boon for things like goblin computers. For most games it probably isn't necessary, but in some games it is.

[EnigmaticHat]

My teacher kinda bailed out on giving me some sites I can use to learn Java, so instead I'm going to ask here.

Where can I learn Java that goes more into detail about it than Code Academy?

Google it. And I'm not even being flippant with this reply.

The web was built by programmers and programmer-kin, so search engines are pretty much better at finding programming information than anything else. Learning to effectively use them to dig up docs, tutorials etc, and ingraining the idea that you can do so is a big part of becoming effective at programming.

Seconded, Stack Exchange (the first result to most programming questions on Google) is a very good teacher.  Pick a program to make (doesn't have to be something new or of any value aside from the experience of learning), code it until you don't know how to do something, Google the problem.  Repeat till the program is done or you've lost all motivation, then pick a harder program and try to make that one.

[i2amroy]

Yeah, but for a game like DF, having predictable pathing is a great boon for things like goblin computers. For most games it probably isn't necessary, but in some games it is.

I don't know what designs you've seen, but pretty much every goblin computer I've seen functions specifically on straight line paths only precisely to avoid issues like this, because if there is only one potential path than they will function identically with and without a nonadmissible heuristic. And if you wanted to say that even 10% of players would take the ability to build goblin computers over the ability to have 2-3x as many creatures on the map at the same time then I would certainly have to disagree with you most strongly. Sure, there may be some sort of "factory line" game or something similar that requires 100% dependable pathfinding (in which case you would use an admissible heuristic), but my main point here is that you, as a developer, need to be aware of the tradeoffs that you are making by deciding that "perfect pathfinding" is a requirement as opposed to just "unnoticeably close to perfect pathfinding" is going to cost you a maximum size factor of 2-3 times for whatever your pathfinding sources are.

In truth there are only three real scenarios that I would see not gaining at least some benefit of a heuristic like that in graph traversal off the top of my head:
1) Having the absolute shortest path actually is an inflexible requirement. For example I'm trying to prove a mathmatical theory, or I really want my missile to have the absolute minimum chance of being shot down. (Note: Honestly the only games I can think of that this falls true for are "production line"-esque games, and most of those just default to preset paths by the player instead of pathfinding to give the player exact control without any game assumptions at all).
2) Other hard constraints limit me to a scenario where the time gained is not necessary. For example if I know there will never be more than 10 units on the field at once, and it's never ever going to be expanded, then I can save my company money by implementing a simpler algorithm that takes less time to implement.
3) Prototyping/plan-once-execute-often code. If you're planning routes or similar during the startup of a program that you then cache for use later then spending a little bit of extra time now can pay big later as those shortest paths get used again and again. For example if I was planning the various transport routes between a company's factories than I would obviously be willing to pay the extra computation time now to have perfect usable routes for as long as they exist.

People often talk about not spending extra time optimizing until you need it, but pathfinding and other NP-hard problems fall into that category where you should really think at least a little bit about optimization right when you start (unless you have a specific reason not to), because they very, very quickly can balloon outwards to consume your whole program's processing power later.

[itisnotlogical]

Remind me to never, ever make decisions ever again once I have something that works. I decided that some enemies in my game just had to have hair physics, and updating the rig to include that borked all my prefabs. Turns out you can't just swap out one mesh for another as long as they have all the same bones. :/

[Spehss _]

So I'm getting a program crash when I try running a function for loading files containing an instance of a class. As far as I know the program saves to files correctly, but it's hard to check really due to the files being binary and all. Creating a new instance of the class and editing that class via editCharacter() seems to work fine. Displays fine. But once the program closes and that temporary working memory is lost, and opening a new instance of the program and attempting to load the file containing that data that supposedly worked fine at first then causes a crash. Same with opening the program, creating a new character, then trying to load a different character file. Crash.

Can't figure out what's wrong. Pretty sure I'm doing something wrong with memory due to my using pointers and getting crashes.

Spoiler: relevant functions (click to show/hide)

Code: [Select]

void saveFile(Character* pointer)
{
string fName=pointer->getName()+".dat";
string fLoc="saves/"+fName;
fstream file(fLoc.c_str(), ios::out|ios::binary);
file.write(reinterpret_cast<char*>(pointer),sizeof(*pointer));
file.close();
}

void loadFile(Character* pointer, string name)
{
string fName=name+".dat";
string fLoc="saves/"+fName;
fstream file(fLoc.c_str(),ios::in|ios::binary);
if(!file)
{
cout<<"Error: \""<<fName<<"\" doesn't exist."<<endl;
file.close();
exit;
}
else
{
pointer=new Character();
file.read(reinterpret_cast<char*>(pointer),sizeof(*pointer));
file.close();
displayCharacter(pointer);
}
}


Spoiler: full program (click to show/hide)

Code: [Select]

#include <iostream>
#include <iomanip>
#include <fstream> //for file input/output
#include <string>
#include "diceRoller.h"
//diceRoller.h contains functions that simulate rolling dice

//diceRoll(int dNum, int dSides) returns an integer total of rolling "dNum" number of dice
//with each dice having "dSides" number of sides
//and adding the results of each die together


//diceRoll(int num) returns the integer result of rolling a single die with "num" number of sides

//seedDice() assigns the value returned by time(0) to srand()
//it seeds the rng, basically

using namespace std;

int rollAttribute();

class Character
{
private:
int level,
str,
dex,
con,
intl,
wis,
cha;
//hpTotal,


string charName, charClass, charRace;

public:
Character();

string getName(){return charName;}
void setName(string n){charName=n;}

string getClass(){return charClass;}
void setClass(string c){charClass=c;}

string getRace(){return charRace;}
void setRace(string r){charRace=r;}

int getLevel(){return level;}
void setLevel(int l){level=l;}

int getStr(){return str;}
int getDex(){return dex;}
int getCon(){return con;}
int getIntl(){return intl;}
int getWis(){return wis;}
int getCha(){return cha;}

void setStr(int s){str=s;}
void setDex(int d){dex=d;}
void setCon(int c){con=c;}
void setIntl(int i){intl=i;}
void setWis(int w){wis=w;}
void setCha(int c){cha=c;}


};

Character::Character()
{
level=str=dex=con=intl=wis=cha=0;
charName="";
charRace="";
charClass="";

}

void displayCharacter(Character* pointer)
{
if(pointer!=0)
{
cout<<"Name: "<<pointer->getName()
<<"\nRace: "<<pointer->getRace()
<<"\nClass: "<<pointer->getClass()
<<"\nLevel: "<<pointer->getLevel()
<<"\nAttributes: "
<<"\n\tStr: "<<pointer->getStr()
<<"\n\tDex: "<<pointer->getDex()
<<"\n\tCon: "<<pointer->getCon()
<<"\n\tInt: "<<pointer->getIntl()
<<"\n\tWis: "<<pointer->getWis()
<<"\n\tCha: "<<pointer->getCha()
<<endl;
}
}

void editCharacter(Character* pointer)
{
char input=' ';
string inString="";
int num=0;
while(input!='q'&&input!='Q')
{
cout<<"\nCharacter Editing Menu: "<<endl;
if((pointer->getName()).length())
cout<<"What would you like to do with "<<pointer->getName()<<"?"<<endl;
else
cout<<"What would you like to do with this unnamed character?"<<endl;
cout<<"A : Edit name"
<<"\nB : Roll attributes"
<<"\nC : Change an attribute"
<<"\nD : Change race"
<<"\nE : Change class"
<<"\nF : Change level"
<<"\nQ : Quit menu"
<<"\n>>";
cin>>input;
switch(input)
{
case 'a':
case 'A': cout<<"\nEnter a name: "; cin>>inString; pointer->setName(inString);
  cout<<"\nName changed to: "<<pointer->getName()<<endl;
  break;
case 'b':
case 'B': pointer->setStr(rollAttribute());
  pointer->setDex(rollAttribute());
  pointer->setCon(rollAttribute());
  pointer->setIntl(rollAttribute());
  pointer->setWis(rollAttribute());
  pointer->setCha(rollAttribute());
  cout<<"Attributes rolled."<<endl;
  break;
case 'c':
case 'C': cout<<"Not implimented yet."<<endl; break;
case 'd':
case 'D': cout<<"\nEnter a race: "; cin>>inString; pointer->setRace(inString);
  cout<<"\nRace changed to: "<<pointer->getRace()<<endl;
  break;
case 'e':
case 'E': cout<<"\nEnter a class: "; cin>>inString; pointer->setClass(inString);
  cout<<"\nClass changed to: "<<pointer->getClass()<<endl;
  break;

case 'f':
case 'F': cout<<"What level is "<<pointer->getName()<<" at now? \n>>";cin>>num; pointer->setLevel(num);
  cout<<"\n"<<pointer->getName()<<" is now level "<<pointer->getLevel();
  break;

case 'q':
case 'Q': break;

default: cout<<"Invalid input."<<endl;
}
}
}

void saveFile(Character* pointer)
{
string fName=pointer->getName()+".dat";
string fLoc="saves/"+fName;
fstream file(fLoc.c_str(), ios::out|ios::binary);
file.write(reinterpret_cast<char*>(pointer),sizeof(*pointer));
file.close();
}

void loadFile(Character* pointer, string name)
{
string fName=name+".dat";
string fLoc="saves/"+fName;
fstream file(fLoc.c_str(),ios::in|ios::binary);
if(!file)
{
cout<<"Error: \""<<fName<<"\" doesn't exist."<<endl;
file.close();
exit;
}
else
{
pointer=new Character();
file.read(reinterpret_cast<char*>(pointer),sizeof(*pointer));
file.close();
displayCharacter(pointer);
}
}

int main()
{
Character* chPoint=0; //pointer for dynamic data
char input=' ';
string current=""; //holds name from current character contained in pointer
seedDice();
cout<<"Welcome to a (completely unofficial) Pathfinder Character Calculator."<<endl;
while(input!='q'&&input!='Q')
{
if(chPoint!=0)
{
current=chPoint->getName();
}
else
current="[No character selected!]";
cout<<"\nMain Menu:"
<<"\nCurrent character: "<<current
<<"\nA : Create new character"
<<"\nB : Load character"
<<"\nC : Edit current character"
<<"\nD : Display current character"
<<"\nQ : Quit program"
<<"\n\n>>";
cin>>input;
switch(input)
{
case 'a':
case 'A': if(chPoint!=0){saveFile(chPoint);delete chPoint; chPoint=0;}
  chPoint=new Character();
  editCharacter(chPoint);
  saveFile(chPoint);
  cout<<sizeof(*chPoint)<<endl;
  break;
case 'b':
case 'B': cout<<"Enter the name of the character to load: ";
  cin>>current;
  if(chPoint!=0)
  {
saveFile(chPoint); //makes sure data from previous character isn't lost
delete chPoint; //clears pointer's memory
chPoint=0;
  }
  loadFile(chPoint, current);
  break;
case 'c':
case 'C': if(chPoint!=0){editCharacter(chPoint);} break;
case 'd':
case 'D': if(chPoint!=0){displayCharacter(chPoint);} break;
case 'q':
case 'Q': break;

default: cout<<"Invalid input."<<endl;
}
}
if(chPoint!=0)
{
delete chPoint;
chPoint=0;
}
return 0;
}

int rollAttribute() //simulates the "roll 4 drop 1 add remainder" method of rolling attributes
{
int rolls[4]; //array to hold dice rolls
for(int i=0;i<4;i++) //loads array with dice rolls
{
rolls[i]=rollDice(6);
//cout<<"Debug:"<<rolls[i]<<endl; //debug
}
int smallest=6, //highest a roll can be is 6
position=0; //position will track where the smallest number is
for(int i=0;i<4;i++) //finds the smallest dice roll in the array
{
if(rolls[i]<smallest)
{
smallest=rolls[i];
position=i;
}
//cout<<"\nDebug:"<<rolls[i]<<endl; //debug
}
rolls[position]=0; //the lowest roll is set to 0 to simulate "dropping" the lowest roll
int total=0;
for(int i=0;i<4;i++)
total+=rolls[i];
return total;
}


Spoiler: diceroll.h (click to show/hide)

Code: [Select]

#include <cstdlib>
#include <ctime>
#ifndef DICEROLL_H
#define DICEROLL_H
using namespace std;

void seedDice()
{
unsigned seed; //rng seed
seed=time(0);
srand(seed);
}

int rollDice(int dSides)
{
return rand()%dSides+1;
}

int rollDice(int dNum, int dSides)
{
//dNum=number of dice to roll
//dSides=number of sides per dice
int total=0;
for(int i=0;i<dNum;i++)
{
total+=rand()%dSides+1;
}

return total;
}
#endif


Including the full program and header file in case anyone wants to compile and run the program themselves. Make sure to make a folder called "saves" in the same directory as where you place the program file and header file.

[Shadowlord]

Pointers point to memory addresses. You're literally writing a memory address to the file and then trying to deference it after loading from the file. It's no surprise that it's crashing.

[EnigmaticHat]

Remind me to never, ever make decisions ever again once I have something that works. I decided that some enemies in my game just had to have hair physics, and updating the rig to include that borked all my prefabs. Turns out you can't just swap out one mesh for another as long as they have all the same bones. :/

This is why you save a backup every time you make any change to old code that would take more than 10 minutes to implement

[itisnotlogical]

The version of the model with hair bones was originally were a separate model file that I thought would be simple to swap in. When I couldn't jam the new model into the old SkinnedMeshRenderer component, I thought that it would be possible to just overwrite the old file and the prefabs would be hunky dory with the changes to the skeleton.

It really wasn't that painful to redo the prefab, it was just kind of tedious to copy all the old colliders and ragdoll stuff that still worked. And the fact that Unity kind of hates the idea of humanoid skeletons having bones that are affected by anything other than the currently active Animator.

[i2amroy]

The version of the model with hair bones was originally were a separate model file that I thought would be simple to swap in. When I couldn't jam the new model into the old SkinnedMeshRenderer component, I thought that it would be possible to just overwrite the old file and the prefabs would be hunky dory with the changes to the skeleton.

It really wasn't that painful to redo the prefab, it was just kind of tedious to copy all the old colliders and ragdoll stuff that still worked. And the fact that Unity kind of hates the idea of humanoid skeletons having bones that are affected by anything other than the currently active Animator.

I'm sorry, I can't help but think "Robot Revolution!" when I see a phrase that begins with "Unity kind of hates the idea of humanoid skeletons having bones".

[miauw62]

Remind me to never, ever make decisions ever again once I have something that works. I decided that some enemies in my game just had to have hair physics, and updating the rig to include that borked all my prefabs. Turns out you can't just swap out one mesh for another as long as they have all the same bones. :/

This is why you save a backup every time you make any change to old code that would take more than 10 minutes to implement

no, this is why you use source control for everything.