Bonjour,
C'est un exemple de pathfinding associé aux ListViews. Ce programme lance une fenetre explorer (si pas choisi le bureau), et 'bordelise' les items pour ensuite calculer les chemins avec A* et les deplace pour les classer par ordre alphabetique.
J'ai utilisé la source de ymca2003 pour le code sur les listviews ("SAUVEGARDE/RESTAURATION des icones du bureau") et la source de MoDDib sur le "A* sans cases".
Si vous voulez augmenter ou baisser la vitesse de deplacement des items, il faut modifier le parametre du Sleep() dans la fonction Pathfinding().
Source / Exemple :
#include <windows.h>
#include <stdlib.h>
#include <math.h>
#include <commctrl.h>
#include <shlobj.h>
#include "resource.h"
#include "liste.h"
#include "pile.h"
#pragma comment(lib, "comctl32.lib")
#define M 10
#define dist(xD, yD, xA, yA) (sqrt((xA - xD) * (xA - xD) + (yA - yD) * (yA - yD)))
RECT rcItem;
LPPOINT lpptDepPosItems, lpptFinPosItems;
HWND hMain, hOther, hList;
HINSTANCE hInst;
HANDLE hHeap;
DWORD dwItemCount, dwMapWidth, dwMapHeight;
int *iSortItem;
char szPath[256], **szName, *szMap;
typedef struct data {
char szClass[16];
HWND *hwnd;
} DATA;
struct coord {
int X;
int Y;
} Direction[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
void DisplayError()
{
LPVOID lpbuf = 0;
DWORD dwerror = GetLastError();
FormatMessage(FORMAT_MESSAGE_ALLOCATE_BUFFER | FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_IGNORE_INSERTS,
NULL, dwerror, MAKELANGID(LANG_NEUTRAL, SUBLANG_NEUTRAL),
(LPTSTR) &lpbuf, 0, NULL);
if(lpbuf) {
MessageBox(GetFocus(), (LPCTSTR)lpbuf, 0, 0x30);
LocalFree(lpbuf);
}
}
int ObtDirectory()
{
BROWSEINFO bi;
ITEMIDLIST *il;
char buff[300];
bi.hwndOwner = hMain;
bi.pidlRoot = NULL;
bi.pszDisplayName = buff;
bi.lpszTitle = "Choisissez un répertoire :";
bi.ulFlags = 0;
bi.lpfn = NULL;
if (NULL == (il = SHBrowseForFolder(&bi))) { DisplayError(); return 0; }
return SHGetPathFromIDList(il, szPath);
}
//Ne trie pas directement les elements, mais place l'ordre correct des chaines dans un tableau
//Tri quicksort (optimisations possibles : suppression de la recursion, meilleur choix de la mediane)
void TriQuick(int g, int d)
{
int i, j, v, u;
if (d - g > M) { //ne trie pas les partitions de taille inferieure a M (10)
v = iSortItem[d]; i = g; j = d;
for ( ; ; ) {
while (stricmp(szName[iSortItem[i]], szName[iSortItem[v]]) < 0 && i < d) i++;
while (stricmp(szName[iSortItem[j]], szName[iSortItem[v]]) > 0 && j > g) --j;
if (j <= i) break;
u = iSortItem[i]; iSortItem[i] = iSortItem[j]; iSortItem[j] = u;
}
u = iSortItem[i]; iSortItem[i] = iSortItem[d]; iSortItem[d] = u;
TriQuick(g, i - 1);
TriQuick(i + 1, d);
}
}
//Tri par insertion
void TriFinal(int dwNumber)
{
int i, j, v;
for (i = 1; i < dwNumber; ++i) {
v = iSortItem[i];
j = i;
while (j > 0 && stricmp(szName[iSortItem[j - 1]], szName[v]) > 0) {
iSortItem[j] = iSortItem[j - 1];
j--;
}
iSortItem[j] = v;
}
}
BOOL CALLBACK EnumProc(HWND hwnd, LPARAM lparam)
{
char szBuf[16];
GetClassName(hwnd, szBuf, 16);
if (!strcmp(szBuf, ((DATA *)lparam)->szClass)) {
- ((DATA *)lparam)->hwnd = hwnd;
return 0;
}
return 1;
}
void PathFinding(DWORD dwCount)
{
DWORD dwCost;
BOOL bExit = 0;
struct noeud *p, *d, *n;
int i, j;
for (i = 0; i < dwCount; ++i) {
SendMessage(hList, LVM_ENSUREVISIBLE, iSortItem[i], 0);
InitialiserListe();
n = malloc(sizeof *n);
n->item.ptPos.x = lpptDepPosItems[iSortItem[i]].x;
n->item.ptPos.y = lpptDepPosItems[iSortItem[i]].y;
n->item.CoutFromDep = 0;
n->item.CoutToEnd = dist(n->item.ptPos.x, n->item.ptPos.y, lpptFinPosItems[iSortItem[i]].x, lpptFinPosItems[iSortItem[i]].y);
n->item.Poids = n->item.CoutFromDep + n->item.CoutToEnd;
n->item.Parent = 0;
InsererFirst(OPEN, n);
while (!ListeVide(OPEN)) {
p = GetBetterNode(OPEN);
if (p->item.ptPos.x == lpptFinPosItems[iSortItem[i]].x && p->item.ptPos.y == lpptFinPosItems[iSortItem[i]].y) {
break;
} else {
for (j = 0; j < 4 && !bExit; ++j) {
int x = p->item.ptPos.x + Direction[j].X;
int y = p->item.ptPos.y + Direction[j].Y;
if (x >= 0 && y >= 0 && x <= dwMapWidth && y <= dwMapHeight) {
d = malloc(sizeof *d);
d->item.ptPos.x = x; d->item.ptPos.y = y;
dwCost = dist(d->item.ptPos.x, d->item.ptPos.y, lpptFinPosItems[iSortItem[i]].x, lpptFinPosItems[iSortItem[i]].y);
if (n = SearchNode(OPEN, d)) {
//Si le poids n'est pas meilleur, on quitte
if (dwCost > n->item.Poids) goto FREE;
//Sinon, on le supprime de OPEN, pour le modifier et ensuite le reinserer
Supprimer(OPEN, n); goto MODIFY;
}
if (SearchNode(CLOSED, d)) goto FREE;
//Ca bugge si l'arrivée est occupée par un item donc on fait une verification la aussi (pas beau mais obligatoire :()
if (x == lpptFinPosItems[iSortItem[i]].x && y == lpptFinPosItems[iSortItem[i]].y) bExit = 1;
if (szMap[y * dwMapWidth + x] == '1' && !bExit) goto FREE;
MODIFY:
d->item.CoutFromDep = p->item.CoutFromDep;
d->item.CoutToEnd = dwCost;
d->item.Poids = d->item.CoutFromDep + d->item.CoutToEnd;
d->item.Parent = p;
InsererFirst(OPEN, d);
FREE: free(d);
}
}
}
InsererFirst(CLOSED, p);
Supprimer(OPEN, p);
bExit = 0;
}
InitialiserPile();
while (p->item.Parent) {
Empiler(p);
p = p->item.Parent;
}
while (!PileVide()) {
p = (struct noeud *)Depiler();
SendMessage(hList, LVM_SETITEMPOSITION, iSortItem[i], MAKELPARAM(p->item.ptPos.x * rcItem.right, p->item.ptPos.y * rcItem.bottom));
SendMessage(hList, LVM_ENSUREVISIBLE, iSortItem[i], 0);
Sleep(5);
}
szMap[lpptDepPosItems[iSortItem[i]].y * dwMapWidth + lpptDepPosItems[iSortItem[i]].x] = 0;
szMap[lpptFinPosItems[iSortItem[i]].y * dwMapWidth + lpptFinPosItems[iSortItem[i]].x] = '1';
DetruirePile();
DetruireListe();
}
}
//Principe du code :
//- Desorganise les icones des listviews explorer et desktop permettant ainsi l'apparition d'obstacles et d'une certaine distance entre point de depart
// et d'arrivée (imaginez si les icones etaient placées comme lors d'une reorganisation automatique, on pourrait pas les faire
// bouger :()
//- Tri par ordre alphabetique : on se sert d'un tableau d'entiers a coté qui va retenir l'ordre des elements, ca
// evite le deplacement de chaines de caracteres longues (donc on y gagne) : c'est une technique de tri par faux pointeurs
//Code largement inspiré de la source de ymca2003 (
http://www.cppfrance.com/code.aspx?id=22940)
//Ne supporte que Win2k/XP
void LaunchPathFinding()
{
STARTUPINFO si = { sizeof(si) };
RECT rcList;
PROCESS_INFORMATION pi;
POINT ptListApprox;
LVITEM lvItem;
LPVOID lpData, lpChar, lplvItem, lpPos, lpRect;
HANDLE hProcess;
DWORD dwProcessId = 0, dwRet, dwStyle, dwDim, dwTemp;
DATA dt;
BOOL bExplorer = 0;
int i, j, k;
char *c = szPath, szCmd[512] = "c:\\WINDOWS\\explorer.exe ";
//Choix du dossier a rearranger
if (!ObtDirectory()) return;
while (*c) c++;
while (*c != '\\') c--;
//L'user a choisi le bureau
if (!strcmp("\\Bureau", c)) {
hOther = FindWindow("ProgMan", 0);
hList = GetTopWindow(GetTopWindow(hOther));
} else {
si.dwFlags = STARTF_USESHOWWINDOW;
si.wShowWindow = SW_SHOWMAXIMIZED;
strcpy(szCmd + 24, szPath);
if (!CreateProcess(0, szCmd, 0, 0, 0, 0, 0, 0, &si, &pi)) { DisplayError(); return; }
//WaitForInputIdle(pi.hProcess, INFINITE); //NE FONCTIONNE PAS (?!)
Sleep(4000);
dt.hwnd = &hOther; strcpy(dt.szClass, "CabinetWClass");
EnumWindows(EnumProc, (LPARAM)&dt);
CloseHandle(pi.hProcess); CloseHandle(pi.hThread);
dt.hwnd = &hList; strcpy(dt.szClass, "SysListView32");
EnumChildWindows(hOther, EnumProc, (LPARAM)&dt);
bExplorer = 1;
}
GetWindowThreadProcessId(hList, &dwProcessId);
dwStyle = GetWindowLong(hList, GWL_STYLE);
if (dwStyle & LVS_AUTOARRANGE) SetWindowLong(hList, GWL_STYLE, dwStyle & (~LVS_AUTOARRANGE));
hProcess = OpenProcess(PROCESS_VM_OPERATION | PROCESS_VM_READ | PROCESS_VM_WRITE, 0, dwProcessId);
if (!hProcess) return;
dwItemCount = SendMessage(hList, LVM_GETITEMCOUNT, 0, 0);
if (!dwItemCount) { MessageBox(0, "Aucun élément dans la listview.", 0, 0); goto Close; }
GetClientRect(hList, &rcList);
dwDim = SendMessage(hList, LVM_APPROXIMATEVIEWRECT, dwItemCount, -1); //si les items ne sont pas tous visibles
ptListApprox.x = dwDim & 0xFFFF;
ptListApprox.y = dwDim >> 16;
if (bExplorer) {
if (rcList.bottom < 5 * ptListApprox.y && rcList.right < 5 * ptListApprox.x) {
rcList.bottom *= 5; rcList.right *= 5;
} else {
rcList.bottom = rcList.bottom < ptListApprox.y ? ptListApprox.y : rcList.bottom;
rcList.right = rcList.right < ptListApprox.x ? ptListApprox.x : rcList.right;
}
}
lpData = VirtualAllocEx(hProcess, 0, sizeof(LVITEM) + sizeof(POINT) + sizeof(RECT) + 256, MEM_COMMIT, PAGE_READWRITE);
if (!lpData) goto Close;
lpChar = (LPBYTE)lpData + sizeof(LVITEM) + sizeof(POINT) + sizeof(RECT);
lpRect = (LPBYTE)lpData + sizeof(LVITEM) + sizeof(POINT);
lplvItem = (LPBYTE)lpData + sizeof(POINT);
lpPos = (LPBYTE)lpData;
lpptDepPosItems = (LPPOINT)HeapAlloc(hHeap, 0, dwItemCount * sizeof(POINT));
if (!lpptDepPosItems) goto VFree;
szName = (char **)HeapAlloc(hHeap, 0, dwItemCount * sizeof(char *));
if (!szName) goto PosFree;
SendMessage(hList, LVM_GETITEMRECT, 0, (LPARAM)lpRect);
ReadProcessMemory(hProcess, lpRect, &rcItem, sizeof(RECT), &dwRet);
rcItem.bottom -= (rcItem.top - 10); rcItem.right -= (rcItem.left - 5); //RECT des items
dwMapWidth = (rcList.right / rcItem.right); dwMapHeight = (rcList.bottom / rcItem.bottom);
szMap = (char *)HeapAlloc(hHeap, HEAP_ZERO_MEMORY, dwMapHeight * dwMapWidth + 1);
if (!szMap) goto SZFree;
for (i = 0; i < dwItemCount; ++i) {
ZeroMemory(&lvItem, sizeof(LVITEM));
lvItem.iItem = i;
lvItem.mask = LVIF_TEXT;
lvItem.cchTextMax = 256;
lvItem.pszText = (char *)lpChar;
WriteProcessMemory(hProcess, lplvItem, &lvItem, sizeof(LVITEM), &dwRet);
szName[i] = (char *)HeapAlloc(hHeap, 0, 256);
SendMessage(hList, LVM_GETITEMTEXT, i, (LPARAM)lplvItem);
ReadProcessMemory(hProcess, lpChar, szName[i], 256, &dwRet);
dwTemp = ((bExplorer) ? ptListApprox.y: ptListApprox.x);
lpptDepPosItems[i].y = dwTemp + (rand() % (rcList.bottom - dwTemp)) / rcItem.bottom * rcItem.bottom;
lpptDepPosItems[i].x = (rand() % rcList.right + 1) / rcItem.right * rcItem.right;
SendMessage(hList, LVM_SETITEMPOSITION, i, MAKELPARAM(lpptDepPosItems[i].x, lpptDepPosItems[i].y));
lpptDepPosItems[i].x /= rcItem.right; lpptDepPosItems[i].y /= rcItem.bottom;
szMap[lpptDepPosItems[i].y * dwMapWidth + lpptDepPosItems[i].x] = '1';
}
//Replace correctement les icones sur la 'grille' de la listview
SendMessage(hList, LVM_ARRANGE, LVA_SNAPTOGRID, 0);
iSortItem = (int *)HeapAlloc(hHeap, 0, dwItemCount * sizeof(int));
if (!iSortItem) goto MFree;
for (i = 0; i < dwItemCount; ++i) iSortItem[i] = i;
TriQuick(0, dwItemCount - 1); //Tri QuickSort
TriFinal(dwItemCount); //Tri par insertion pour finir le boulot
//On determine maintenant les coordonnées que vont devoir atteindre les items
lpptFinPosItems = (LPPOINT)HeapAlloc(hHeap, 0, dwItemCount * sizeof(POINT));
if (!lpptFinPosItems) goto SFree;
lpptFinPosItems[iSortItem[0]].x = 0;
lpptFinPosItems[iSortItem[0]].y = 0;
for (i = 1; i < dwItemCount; ++i) {
k = iSortItem[i]; j = iSortItem[i - 1];
lpptFinPosItems[k].y = lpptFinPosItems[j].y;
if (lpptFinPosItems[j].x >= rcList.right - 2 * rcItem.right) {
lpptFinPosItems[k].x = 2;
lpptFinPosItems[k].y += rcItem.bottom;
} else lpptFinPosItems[k].x = lpptFinPosItems[j].x + rcItem.right;
}
for (i = 1; i < dwItemCount; ++i) {
lpptFinPosItems[iSortItem[i]].x /= rcItem.right; lpptFinPosItems[iSortItem[i]].y /= rcItem.bottom;
}
//On a les coordonnées de debut et de fin, les dimensions des cases (rcItem),
//on lance alors le pathfinding
PathFinding(dwItemCount);
HeapFree(hHeap, 0, lpptFinPosItems);
SFree:
HeapFree(hHeap, 0, iSortItem);
MFree:
HeapFree(hHeap, 0, szMap);
for (i = 0; i < dwItemCount; i++)
HeapFree(hHeap, 0, szName[i]);
SZFree:
HeapFree(hHeap, 0, szName);
PosFree:
HeapFree(hHeap, 0, lpptDepPosItems);
VFree:
VirtualFreeEx(hProcess, lpData, 0, MEM_RELEASE);
Close:
CloseHandle(hProcess);
}
BOOL CALLBACK DlgProc(HWND hwnd, UINT message, WPARAM wparam, LPARAM lparam)
{
switch (message) {
case WM_INITDIALOG:
hMain = hwnd;
hHeap = GetProcessHeap();
srand(GetTickCount());
SetClassLong(hwnd, GCL_HICON, (long)LoadIcon(0, IDI_APPLICATION));
return 1;
case WM_COMMAND:
switch (wparam) {
case IDOK:
ShowWindow(hwnd, SW_HIDE);
LaunchPathFinding();
ShowWindow(hwnd, SW_SHOW);
break;
case IDCANCEL:
EndDialog(hwnd, 0);
break;
}
return 0;
}
return 0;
}
int __stdcall WinMain(HINSTANCE hInstance, HINSTANCE p, LPSTR q, int r)
{
hInst = hInstance;
DialogBoxParam(hInst, (LPCTSTR)IDD_PATH, 0, DlgProc, 0);
return 0;
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.